题目描述

给定一个正整数 x，我们将会写出一个形如 x (op1) x (op2) x (op3) x ... 的表达式，其中每个运算符 op1，op2 等可以是加、减、乘、除（+，-，*，或是 /）之一。例如，对于 x = 3，我们可以写出表达式 3 * 3 / 3 + 3 - 3，该式的值为 3 。

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

1. 除法运算符（/）返回有理数。
2. 任何地方都没有括号。
3. 我们使用通常的操作顺序：乘法和除法发生在加法和减法之前。
4. 不允许使用一元否定运算符（-）。例如，x - x 是一个有效的表达式，因为它只使用减法，但是 -x + x 不是，因为它使用了否定运算符。

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

样例

输入：x = 3, target = 19
输出：5
解释：3 * 3 + 3 * 3 + 3 / 3 。表达式包含 5 个运算符。

输入：x = 5, target = 501
输出：8
解释：5 * 5 * 5 * 5 - 5 * 5 * 5 + 5 / 5 。表达式包含 8 个运算符。

输入：x = 100, target = 100000000
输出：3
解释：100 * 100 * 100 * 100 。表达式包含 3 个运算符。

注意

• 2 <= x <= 100
• 1 <= target <= 2 * 10^8

算法

(递归 / 记忆化搜索) $O(\log^2 target)$

1. 我们可以只考虑每次加上或者减去一个数，这个数为 1, x, x^2, x^3, ...。相当于按 x 进制表示 target，但不同点是进制位上允许负数。
2. 不妨从最低位，即需要多少个 1 开始考虑，假设 target 模 x 的余数为 r，此时有两种选择：
   * 加上 r 个 1，此时问题可以转为到次低位，然后考虑 x 的个数。这可以看做 target = target / x，然后重新变到最低位考虑。
   * 减去 x - r 个 1，此时问题同样转到次低位，然后考虑 x 的个数。这可以看做 target = target/x + 1（这里加 1 时因为最低位补全了一个完整的 x）。然后重新变到到最低位考虑。
3. 递归出口为 target 为 1 时，只需要补一个 x^depth；当 target 为 0 时，我们不需要加上或减去任何数字。出口前，需要去除最开头的正好。
4. 这里可以采用一个哈希表，来记录递归过程中出现的重复状态，即 target 在 depth 层时所需要的最少操作符数量。

时间复杂度

• 每一层我们访问到的 target 最多就只有两个。我们每次都会将 target 除掉 x，一个上取整，一个下取整，结果最多差 1。
• target/x 与 target/x+1 再进行递归时，最多只会再分出一个新分支。这里共 $\log target$ 层，每层比上一层多出一个新分支，所以时间复杂度为 $O(\log^2 target)$。

空间复杂度

• 和时间复杂度一致。

C++ 代码

class Solution {
public:
    unordered_map<string, int> seen;

    int solve(int x, int cur, int depth) {
        if (cur == 0)
            return -1;          // -1 为去除开头的正号。

        int usage = depth;
        if (depth == 0) {
            usage = 2;
        }

        if (cur == 1)
            return usage - 1;  // -1 为去除开头的正号。

        string pr(to_string(depth) + " " + to_string(cur));
        if (seen.find(pr) != seen.end())
            return seen[pr];

        int div = cur / x, r = cur % x;
        if (r == 0)
            return seen[pr] = solve(x, div, depth + 1);

        return seen[pr] = min(
            solve(x, div, depth+1)+usage*r,
            solve(x, div+1, depth+1)+usage*(x-r)
        );
    }

    int leastOpsExpressTarget(int x, int target) {
        return solve(x, target, 0);
    }
};

Go 代码

func leastOpsExpressTarget(x int, target int) int {
    seen := make(map[string]int)
    var solve func(cur, depth int) int

    solve = func(cur, depth int) int {
        if cur == 0 {
            return -1            // -1 为去除开头的正号。
        }

        usage := depth
        if depth == 0 {
            usage = 2
        }

        if cur == 1 {
            return usage - 1     // -1 为去除开头的正号。
        }

        key := fmt.Sprintf("%d_%d", cur, depth)
        if v, ok := seen[key]; ok {
            return v
        }

        div, r := cur/x, cur%x
        if r == 0 {
            seen[key] = solve(div, depth+1)
        } else {
            seen[key] = min(solve(div, depth+1)+usage*r, solve(div+1, depth+1)+usage*(x-r))
        }

        return seen[key]
    }

    return solve(target, 0)
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}