964. 表示数字的最少运算符 #

问题描述#

给定一个正整数 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^8

解题思路#

问题就是将 \(\text{target}\) 表示为

\[ \text{target}=a_0 \cdot x^0 + a_1 \cdot x^1 + \cdots + a_n \cdot x^n \]

其中 \(x^0=\boxed{x\div x}\)，\(0\le\vert a_i \vert \lt x\)，即 \(a_i\) 可正、可负、可为 0。

当 \(i=0\) 时，\(\boxed{\pm x^0}=\boxed{\pm x\div x}\) 需要 2 个运算符，所以 \(a_0x^0\) 需要 \(2a_0\) 个运算符；

当 \(i=1\) 时，\(\boxed{\pm x^1}=\boxed{\pm x}\) 需要 1 个运算符，所以 \(a_1x^1\) 需要 \(a_1\times 1\) 个运算符；

当 \(i=2\) 时，\(\boxed{\pm x^2}=\boxed{\pm x\times x}\) 需要 2 个运算符，所以 \(a_2x^2\) 需要 \(a_2\times 2\) 个运算符；

同理，当 \(i>=1\) 时，\(a_ix^i\) 需要 \(a_i\times i\) 个运算符。

所以需要的总的运算符数量为:

\[ 2a_0+\sum_{i=1}^n a_i\times i-1. \]

减去 1 是因为，表达式前面的运算符可以去掉，将一个为正的 \(a_i\) 放在首位即可。

因为 \(a_i\) 可正可负，而根据等式:

\[ \text{target}=a_0 x^0 + a_1 x^1 + \cdots + a_n x^n \]

当 \(a_i\) 为正时，\(a_i^+=\frac{\text{target}}{x^i}\bmod x\)，此时相当于 \(\text{target}-a_i^+ x^i\)。

当 \(a_i\) 为负时，\(a_i^-=\frac{\text{target}}{x^i}\bmod (-x)=-(x-a_i^+)\)，此时相当于 \(\text{target}+(x-a_i^+)x^i\)。

所以整个过程就相当于搜索一棵二叉树。

\[ \text{target}\to \begin{cases} \text{target}=\text{target}-a_0^+x^0\to \begin{cases} \text{target}=\text{target}-a_1^+x^1\\ \text{target}=\text{target}+(x-a_1^+)x^1\\ \end{cases}\cdots\\ \text{target}=\text{target}+(x-a_0^+)x^0\to \begin{cases} \text{target}=\text{target}-a_1^+x^1\\ \text{target}=\text{target}+(x-a_1^+)x^1\\ \end{cases}\cdots \end{cases} \]

from functools import lru_cache
import math


class Solution:
    def leastOpsExpressTarget(self, x: int, target: int) -> int:
        n = int(math.log(target, x)) + 1  # 二叉树的高度
        ops = [i for i in range(n + 1)]  # 每一层需要的运算符数量
        pows = [x ** i for i in range(n + 1)]

        ops[0] = 2  # x/x 需要两个

        @lru_cache
        def f(i: int, target: int) -> int:
            if i > n:
                return float("INF")
            if target == 0:
                return 0
            if target == x ** i:
                return ops[i]

            ai = (target // pows[i]) % x

            return min(
                ai * ops[i] + f(i + 1, target - ai * pows[i]),
                (x - ai) * ops[i] + f(i + 1, target + (x - ai) * pows[i]),
            )

        return f(0, target) - 1

964. 表示数字的最少运算符#

问题描述#

解题思路#

964. 表示数字的最少运算符 #