2023-05-25：给定一个正整数x，我们将会写出一个形如

2023-05-25：给定一个正整数 x，我们将会写出一个形如 x (op1) x (op2) x (op3) x ... 的表达式

其中每个运算符 op1，op2，… 可以是加、减、乘、除之一

例如，对于 x = 3，我们可以写出表达式 3 * 3 / 3 + 3 - 3，该式的值为3

在写这样的表达式时，我们需要遵守下面的惯例：

除运算符（/）返回有理数

任何地方都没有括号

我们使用通常的操作顺序：乘法和除法发生在加法和减法之前

不允许使用一元否定运算符（-）。例如，“x - x” 是一个有效表达

因为它只使用减法，但是 “-x + x” 不是，因为它使用了否定运算符

我们希望编写一个能使表达式等于给定的目标值 target 且运算符最少的表达式。

返回所用运算符的最少数量。

输入：x = 5, target = 501。

输出：8。

答案2023-05-25：

大体过程如下：

1.定义函数 leastOpsExpressTarget，传入参数 x 和 target。

2.初始化一个 map 类型的变量 dp，用于记录已经计算过的结果。

3.调用函数 dpf，传入参数 0、target、x 和 dp。函数 dpf 的作用是计算在当前情况下，target 最少需要几个运算符才能被表达出来。

4.在函数 dpf 中，首先判断当前情况是否已经计算过，如果已经计算过则直接返回结果。

5.如果没有计算过，则根据题目要求，最多只能使用 x 的 i 次方来进行运算，所以需要记录当前来到了 x 的 i 次方这个数字。

6.如果 target 大于 0 且 i 小于 39（为了防止溢出），则根据题目要求，将 target 分解成商和余数两部分，然后分别计算用加、减、乘、除运算符可以得到的最小的运算次数。

7.最后，将计算出的结果保存到 dp 中，并返回该结果。

8.定义函数 cost，传入参数 i，用于得到 x 的 i 次方这个数字需要几个运算符，默认前面再加个'+'或'-'。

9.定义函数 min，传入参数 a 和 b，用于比较 a 和 b 的大小，并返回较小的值。

10.在主函数 main 中，定义变量 x 和 target，分别赋值为 5 和 501。然后调用函数 leastOpsExpressTarget，并将结果输出。

时间复杂度：

• 函数 leastOpsExpressTarget 中调用了函数 dpf，而函数 dpf 的时间复杂度为 O(log(target))（因为 i 最大可以达到 39，x^39 已经大于等于 target），所以最终的时间复杂度为 O(log(target))。

空间复杂度：

• 函数 leastOpsExpressTarget 中创建了一个 map 类型的变量 dp，其中存储的元素个数最多为 O(log(target) * 40)，所以空间复杂度为 O(log(target))。

go完整代码如下：

package main

import (

"fmt"

)

func leastOpsExpressTarget(x, target int) int {

dp := make(map[int]map[int]int)

return dpf(0, target, x, dp) - 1

}

// i : 当前来到了x的i次方

// target : 认为target只能由x的i次方，或者更高次方来解决，不能使用更低次方！

// 返回在这样的情况下，target最少能由几个运算符搞定！

// (3, 1001231) -> 返回值！

// dp.get(3) ->

func dpf(i, target, x int, dp map[int]map[int]int) int {

if val, ok := dp[i][target]; ok {

return val

}

ans := 0

if target > 0 && i

if target == 1 {

ans = cost(i)

} else {

div := target / x

mod := target % x

p1 := mod*cost(i) + dpf(i+1, div, x, dp)

p2 := (x-mod)*cost(i) + dpf(i+1, div+1, x, dp)

ans = min(p1, p2)

}

}

if _, ok := dp[i]; !ok {

dp[i] = make(map[int]int)

}

dp[i][target] = ans

return ans

}

// 得到x的i次方这个数字

// 需要几个运算符，默认前面再加个'+'或'-'

func cost(i int) int {

if i == 0 {

return 2

}

return i

}

func min(a, b int) int {

if a < b {

return a

}

return b

}

func main() {

x := 5

target := 501

fmt.Println(leastOpsExpressTarget(x, target))

}

在这里插入图片描述

rust完整代码如下：

use std::collections::HashMap;

fn least_ops_express_target(x: i32, target: i32) -> i32 {

let mut dp: HashMap

dpf(0, target, x, &mut dp) - 1

}

// i : 当前来到了x的i次方

// target : 认为target只能由x的i次方，或者更高次方来解决，不能使用更低次方！

// 返回在这样的情况下，target最少能由几个运算符搞定！

// (3, 1001231) -> 返回值！

// dp.get(3) ->

fn dpf(i: i32, target: i32, x: i32, dp: &mut HashMap

if let Some(map) = dp.get(&i) {

if let Some(val) = map.get(&target) {

return *val;

}

}

let ans: i32;

if target > 0 && i

if target == 1 {

ans = cost(i);

} else {

let div = target / x;

let mod0 = target % x;

let p1 = mod0 * cost(i) + dpf(i + 1, div, x, dp);

let p2 = (x - mod0) * cost(i) + dpf(i + 1, div + 1, x, dp);

ans = p1.min(p2);

}

} else {

ans = 0;

}

dp.entry(i).or_insert(HashMap::new()).insert(target, ans);

ans

}

// 得到x的i次方这个数字

// 需要几个运算符，默认前面再加个'+'或'-'

fn cost(i: i32) -> i32 {

if i == 0 {

2

} else {

i

}

}

fn main() {

let x = 3;

let target = 19;

println!("{}", least_ops_express_target(x, target));

let x = 5;

let target = 501;

println!("{}", least_ops_express_target(x, target));

let x = 100;

let target = 100000000;

println!("{}", least_ops_express_target(x, target));

}

在这里插入图片描述

c语言完整代码如下：

#include

#include

int leastOpsExpressTarget(int x, int target);

int cost(int i);

int dpf(int i, int target, int x, int*** dp) {

if (dp[i][target] != 0) {

return dp[i][target];

}

int ans = 0;

if (target > 0 && i

if (target == 1) {

ans = cost(i);

}

else {

int div = target / x;

int mod = target % x;

int p1 = mod * cost(i) + dpf(i + 1, div, x, dp);

int p2 = (x - mod) * cost(i) + dpf(i + 1, div + 1, x, dp);

ans = p1 < p2 ? p1 : p2;

}

}

dp[i][target] = ans;

return ans;

}

int leastOpsExpressTarget(int x, int target) {

int** dp = (int**)calloc(40, sizeof(int*));

for (int i = 0; i < 40; ++i) {

dp[i] = (int*)calloc(target + 1, sizeof(int));

}

int ans = dpf(0, target, x, dp) - 1;

for (int i = 0; i < 40; ++i) {

free(dp[i]);

}

free(dp);

return ans;

}

// 得到x的i次方这个数字

// 需要几个运算符，默认前面再加个'+'或'-'

int cost(int i) {

return i == 0 ? 2 : i;

}

int main() {

int x = 5;

int target = 501;

printf("%d\n", leastOpsExpressTarget(x, target));

return 0;

}

在这里插入图片描述

c++完整代码如下：

#include

#include

using namespace std;

int cost(int i);

int dpf(int i, int target, int x, unordered_map

if (dp.count(i) && dp[i].count(target)) {

return dp[i][target];

}

int ans = 0;

if (target > 0 && i

if (target == 1) {

ans = cost(i);

}

else {

int div = target / x;

int mod = target % x;

int p1 = mod * cost(i) + dpf(i + 1, div, x, dp);

int p2 = (x - mod) * cost(i) + dpf(i + 1, div + 1, x, dp);

ans = min(p1, p2);

}

}

if (!dp.count(i)) {

dp[i] = unordered_map();

}

dp[i][target] = ans;

return ans;

}

int leastOpsExpressTarget(int x, int target) {

unordered_map

return dpf(0, target, x, dp) - 1;

}

// 得到x的i次方这个数字

// 需要几个运算符，默认前面再加个'+'或'-'

int cost(int i) {

return i == 0 ? 2 : i;

}

int main() {

int x = 5;

int target = 501;

cout << leastopsexpresstarget(x, target)

return 0;

}

在这里插入图片描述