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，并将结果输出。
时间复杂度：
空间复杂度：
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) -> {1001231 对应的value}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 < 39 { 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<i32, HashMap<i32, i32>> = HashMap::new(); dpf(0, target, x, &mut dp) - 1}
// i : 当前来到了x的i次方// target : 认为target只能由x的i次方，或者更高次方来解决，不能使用更低次方！// 返回在这样的情况下，target最少能由几个运算符搞定！// (3, 1001231) -> 返回值！// dp.get(3) -> {1001231 对应的value}fn dpf(i: i32, target: i32, x: i32, dp: &mut HashMap<i32, HashMap<i32, i32>>) -> i32 { if let Some(map) = dp.get(&i) { if let Some(val) = map.get(&target) { return *val; } }
let ans: i32; if target > 0 && i < 39 { 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 <stdio.h>#include <stdlib.h>
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 < 39) { 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 <iostream>#include <unordered_map>
using namespace std;
int cost(int i);
int dpf(int i, int target, int x, unordered_map<int, unordered_map<int, int>>& dp) { if (dp.count(i) && dp[i].count(target)) { return dp[i][target]; }
int ans = 0; if (target > 0 && i < 39) { 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<int, int>(); } dp[i][target] = ans; return ans;}
int leastOpsExpressTarget(int x, int target) { unordered_map<int, unordered_map<int, int>> dp; 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) << endl; return 0;}
复制代码
评论