表示数字的最少运算符

难度: Hard

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

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

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

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

示例 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⁸

Submission

运行时间: 32 ms

内存: 0.0 MB

class Solution:
    def leastOpsExpressTarget(self, x, y):
        pos = neg = k = 0
        while y:
            y, cur = divmod(y, x)
            if k:
                pos, neg = min(cur * k + pos, (cur + 1) * k + neg), min((x - cur) * k + pos, (x - cur - 1) * k + neg)
            else:
                pos, neg = cur * 2, (x - cur) * 2
            k += 1
        return min(pos, k + neg) - 1

Explain

该题解采用动态规划方法，通过计算当前数值能被表示的最小操作数，逐步递推至目标值。利用正数（pos）和负数（neg）两个变量，分别记录达到当前数值的最小正表达式和最小负表达式所需的运算符数量。通过不断地对目标值 target 进行 x 的除法，计算每步的余数以决定使用加法或乘法的数量，同时也考虑通过余数来决定是否可以通过少量的减法或除法来达到目标。最后，根据最终得到的 pos 和 neg 的值，计算出包括转换方向的运算符总数，并减去一个基础值，得到最小运算符的总数。

时间复杂度: O(log_x(target))

空间复杂度: O(1)

class Solution:
    def leastOpsExpressTarget(self, x, y):
        pos = neg = k = 0  # 初始化 pos 和 neg 为0，k 用于追踪 x 的幂次
        while y:
            y, cur = divmod(y, x)  # 使用除法和取余确定当前目标的最小表示
            if k:
                # 更新 pos 和 neg 以表示最小的运算符数量
                pos, neg = min(cur * k + pos, (cur + 1) * k + neg), min((x - cur) * k + pos, (x - cur - 1) * k + neg)
            else:
                # 初始化情况，只有 x 与 target 相差一个乘法的情况
                pos, neg = cur * 2, (x - cur) * 2
            k += 1  # 增加 x 的幂次
        return min(pos, k + neg) - 1  # 选择 pos 和 neg 中较小的，减去基础值以修正最终结果

Explore

在动态规划中，通过每次迭代更新的方式来确保每一步的最小表示都是最优的。在每次迭代中，我们都会根据当前的余数来选择是增加还是减少操作数。通过逐步构建从基数x到target的最小操作路径，并在每次迭代中考察所有可能的操作（加法、减法、乘法），保证了每一步的决策都是在当前条件下最优的。这种方法利用了动态规划的特性，即通过局部最优解的累积来达到全局最优解。

在更新pos和neg的过程中，min函数用于选择达到当前数字的最少运算符数量。对于pos，其选项`cur * k + pos`代表如果直接使用加法达到当前数字所需的操作数，而`(cur + 1) * k + neg`代表通过稍微超过当前数字后再减少一些的操作数。对于neg，`(x - cur) * k + pos`表示尝试达到稍大于当前数字然后减少的方式，而`(x - cur - 1) * k + neg`代表从更大的数减少更多以达到当前数字的操作数。这些计算考虑了所有可能的方式来最小化运算符的使用，确保每一步都是最优的。

在k为0的初始情况下，pos和neg设置为cur*2和(x-cur)*2是因为这是构建初始状态时的基本操作数。这里的乘以2代表了构建当前数字的基础运算符数（1次乘法和1次加法或减法）。例如，使用x的1次方（即x本身）来表达cur需要cur次加法，因为要加cur次x，而每次加法都需要一个操作符。同样地，使用x的1次方表达x-cur需要(x-cur)次减法。所以，乘以2反映了这两种基础操作的运算符数量。

在最后返回结果时，从min(pos, k + neg)的结果中减去1是为了调整最后的运算符总数，确保不计算多余的加法或乘法转换。由于在算法的开始阶段，我们初始化了pos和neg的值来反映基础操作，这些操作已经包括了从0开始构建表达式所需的运算符。因此，在最终计算完成后，需要减去这个最初的基础操作（通常是一个额外的乘法），以得到精确的最小运算符总数。