Hard

题目描述

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

当写这样的表达式时，我们遵循以下约定：

  • 除法运算符 (/) 返回有理数。
  • 任何地方都不放括号。
  • 我们使用通常的运算顺序：乘法和除法发生在加法和减法之前。
  • 不允许使用一元否定运算符 (-)。例如，"x - x" 是一个有效的表达式，因为它只使用减法，但 “-x + x” 无效，因为它使用了否定。

我们希望写一个运算符数最少的表达式，使得表达式等于给定的目标值。返回使用的最少运算符数。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

解题思路

这是一个非常有挑战性的数学动态规划问题。核心思想是将目标数字用 x 的不同幂次来表示。

我们可以将问题转化为：用 x 的各次幂（x^0, x^1, x^2, …）的线性组合来表示目标数字，每个系数可以是正数或负数。关键观察是：

  • x^0 = 1 需要 2 个运算符（x/x）
  • x^1 = x 需要 0 个运算符
  • x^k (k≥2) 需要 k-1 个运算符

我们使用递归+记忆化搜索，状态是当前的目标值。对于每个状态，我们尝试所有可能的 x^k 的系数，选择使总运算符数最小的方案。

具体策略：

  1. 找到最大的 x^k ≤ target
  2. 尝试用若干个 x^k 来逼近 target
  3. 对于剩余部分，递归求解
  4. 同时考虑用 x^(k+1) 减去一些值来达到 target 的情况

为了避免系数过大，我们限制每个 x^k 的系数不超过 x。

代码实现

class Solution {
public:
    unordered_map<int, int> memo;
    int x;
    
    int dp(int i, int target) {
        if (target == 0) return 0;
        if (i >= 32) return 1e9;
        
        int key = i * 1000000000LL + target;
        if (memo.count(key)) return memo[key];
        
        long long cur = 1;
        for (int j = 0; j < i; j++) cur *= x;
        
        if (cur > target) {
            memo[key] = 1e9;
            return 1e9;
        }
        
        int cost = (i == 0) ? 2 : i;
        int ans = 1e9;
        
        // 不使用 x^i
        ans = min(ans, dp(i + 1, target));
        
        // 使用 k 个 x^i
        for (int k = 1; k <= min((long long)x, target / cur + 1); k++) {
            int remain = target - k * cur;
            if (remain >= 0) {
                ans = min(ans, k * cost + (k - 1) + dp(i + 1, remain));
            }
        }
        
        memo[key] = ans;
        return ans;
    }
    
    int leastOpsExpressTarget(int x, int target) {
        this->x = x;
        memo.clear();
        return dp(0, target);
    }
};

class Solution:
    def leastOpsExpressTarget(self, x: int, target: int) -> int:
        from functools import lru_cache
        
        @lru_cache(maxsize=None)
        def dp(i, cur):
            if cur == 0:
                return 0
            if i >= 32:
                return float('inf')
            
            if x ** i > cur:
                return float('inf')
            
            # cost of x^i
            if i == 0:
                cost = 2  # x / x
            else:
                cost = i  # x * x * ... (i times)
            
            ans = float('inf')
            
            # don't use x^i
            ans = min(ans, dp(i + 1, cur))
            
            # use k copies of x^i
            for k in range(1, min(x, cur // (x ** i)) + 2):
                remain = cur - k * (x ** i)
                if remain >= 0:
                    # k * cost for k copies of x^i
                    # (k-1) for (k-1) '+' operators
                    ans = min(ans, k * cost + max(0, k - 1) + dp(i + 1, remain))
            
            return ans
        
        return dp(0, target)

public class Solution {
    private Dictionary<string, int> memo = new Dictionary<string, int>();
    private int x;
    
    private int Dp(int i, int target) {
        if (target == 0) return 0;
        if (i >= 32) return int.MaxValue / 2;
        
        string key = i + "," + target;
        if (memo.ContainsKey(key)) return memo[key];
        
        long cur = 1;
        for (int j = 0; j < i; j++) {
            if (cur > int.MaxValue / x) {
                cur = long.MaxValue;
                break;
            }
            cur *= x;
        }
        
        if (cur > target) {
            memo[key] = int.MaxValue / 2;
            return int.MaxValue / 2;
        }
        
        int cost = (i == 0) ? 2 : i;
        int ans = int.MaxValue / 2;
        
        // don't use x^i
        ans = Math.Min(ans, Dp(i + 1, target));
        
        // use k copies of x^i
        long maxK = Math.Min(x, target / cur + 1);
        for (int k = 1; k <= maxK; k++) {
            int remain = target - k * (int)cur;
            if (remain >= 0) {
                ans = Math.Min(ans, k * cost + Math.Max(0, k - 1) + Dp(i + 1, remain));
            }
        }
        
        memo[key] = ans;
        return ans;
    }
    
    public int LeastOpsExpressTarget(int x, int target) {
        this.x = x;
        memo.Clear();
        return Dp(0, target);
    }
}

var leastOpsExpressTarget = function(x, target) {
    const memo = new Map();
    
    function dp(cur, target) {
        if (target === 0) return 0;
        if (cur >= 40) return Math.min(target * 2, (x - target) * 2);
        
        const key = cur * 1000000000 + target;
        if (memo.has(key)) return memo.get(key);
        
        let result;
        if (cur >= target) {
            result = Math.min(target * cur, (x - target) * cur);
        } else {
            const pos = Math.floor(target / cur);
            const neg = pos + 1;
            const remainder = target - pos * cur;
            const excess = neg * cur - target;
            
            result = Math.min(
                pos + dp(cur, remainder),
                neg + dp(cur, excess)
            );
        }
        
        memo.set(key, result);
        return result;
    }
    
    return dp(1, target) - 1;
};

Wait, let me reconsider this problem with the correct approach:

var leastOpsExpressTarget = function(x, target) {
    const memo = {};
    
    function dp(i, target) {
        if (target === 0) return 0;
        if (i >= 40) return Math.min(target * 2, (target - 1) * 2 + 1);
        if (target === 1) return Math.min(2, i);
        
        const key = i + ',' + target;
        if (memo[key] !== undefined) return memo[key];
        
        const cur = Math.pow(x, i);
        let result;
        
        if (target < cur) {
            result = Math.min(target * i, (cur - target) * i + i);
        } else {
            const quotient = Math.floor(target / cur);
            const remainder = target % cur;
            
            result = Math.min(
                quotient * i + dp(i + 1, remainder),
                (quotient + 1) * i + dp(i + 1, cur - remainder)
            );
        }
        
        return memo[key] = result;
    }
    
    return dp(0, target) - 1;
};

Actually, let me fix this with the proper recursive approach:

var leastOpsExpressTarget = function(x, target) {
    const memo = {};
    
    function helper(cur, target) {
        if (target === 0) return 0;
        if (cur >= 32) return target + 1;
        if (target === 1) return Math.min(2, cur + 1);
        
        const key = cur + ',' + target;
        if (memo[key] !== undefined) return memo[key];
        
        const power = Math.pow(x, cur);
        let result;
        
        if (power > target) {
            result = Math.min(
                target * cur + target,
                (power - target) * cur + helper(cur + 1, power - target)
            );
        } else {
            const quotient = Math.floor(target / power);
            const remainder = target % power;
            
            result = Math.min(
                remainder * cur + quotient + helper(cur + 1, remainder),
                (power - remainder) * cur + quotient + 1 + helper(cur + 1, power - remainder)
            );
        }
        
        return memo[key] = result;
    }
    
    return helper(0, target) - 1;
};

Let me provide the correct solution:

var leastOpsExpressTarget = function(x, target) {
    let pos = neg = k = pos2 = neg2 = 0;
    
    while (target) {
        target = Math.floor(target / x);
        const remainder = target % x;
        
        if (k) {
            const mini = Math.min(remainder * k + pos, (remainder + 1) * k + neg);
            const maxi = Math.min((x - remainder) * k + pos2, (x - remainder - 1) * k + neg2);
            pos2 = pos;
            neg2 = neg;
            pos = mini;
            neg = maxi;
        } else {
            pos2 = pos = remainder * 2;
            neg2 = neg = (x - remainder) * 2;
        }
        k++;
    }
    
    return Math.min(k + neg, pos - 1);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(log_x(target) × target × x)状态数量为 O(log_x(target) × target)，每个状态需要尝试 O(x) 种选择
空间复杂度O(log_x(target) × target)记忆化存储的状态数量