《剑指 offer》刷题记录之七：动态规划与贪婪算法

发表于 分类于 ， 阅读次数： 本文字数： 2.1k 阅读时长 ≈ 7 分钟

本篇博客为《剑指 offer》一书的刷题笔记（第七部分）。

动态规划是编程面试中的热门话题。一般来说，能够用动态规划求解的问题具有如下三个特点：

  1. 问题的目标是求一个问题的最优解（通常是求最大值或最小值）
  2. 该问题能够分解为若干个子问题，整体问题的最优解依赖各个子问题的最优解
  3. 这些子问题之间还有相互重叠的更小的子问题

由于子问题在分解大问题的过程中重复出现，为了避免重复求解子问题，我们可以用从下往上的顺序先计算小问题的最优解并存储下来，再以此为基础求取大问题的最优解。简单来说就是从上往下分析问题，从下往上求解问题。

与动态规划不一样，当应用贪婪算法解决问题时，每一步都可以做出一个贪婪的选择，基于这个选择，我们确定能够得到最优解。关于贪婪算法的正确性需要依赖于数学证明。

面试题 14：剪绳子

题目：给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

示例

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

限制：

  • 2 <= n <= 58

思路及代码

我们首先尝试用动态规划方法解决这个问题。定义 \(f(n)\) 为把长度为 \(n\) 的绳子剪成若干段后各段长度乘积的最大值，则我们可以将该问题分解为如下子问题： \[ f(n)=\max (f(i) \times f(n-i)) \] 其中 \(0 < i < n\)。这是一个自上到下的递归公式，其中包含很多重复的子问题。为了避免大量不必要的计算。我们可以自下而上计算，将每个 \(f(i)\) 存储起来，直到得到 \(f(n)\)。

需要注意的是，由于题目要求绳子必须要剪，所以对于 \(n<=3\) 的情况需要单独讨论，因为其不剪的状态下得到的乘积要大于剪后的任意组合的乘积（实际上这一阈值的选择需要数学证明）。

本方法的 java 实现如下：

class Solution {
    public int cuttingRope(int n) {
        if (n <= 3) return n - 1; // 处理特殊情况    
        int dp[] = new int[n + 1]; // 数组存储 1-n 下的最优解
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3; // 注意前 3 个的值并不是输出结果
        for (int i = 4; i <= n; i++) { // 从 4 开始
            int max = 0;
            for (int j = 1; j <= i/2; j++) { // 由于乘法交换律，j 只要遍历一半即可
                max = Math.max(max, dp[j] * dp[i - j]);
            }
            dp[i] = max;
        }
        return dp[n];
    }
}

易知该方法的时间复杂度为 \(O(n^2)\)，空间复杂度为 \(O(n)\)。

这道题还可以使用贪婪算法解决。我们需要用数学方法找出优先级最高的切分长度。首先，基于均值不等式可以得到： \[ \frac{n_{1}+n_{2}+\ldots+n_{a}}{a} \geq \sqrt[a]{n_{1} n_{2} \ldots n_{a}} \] 即将绳子分为 \(a\) 段时，当且仅当 \(n_{1}=n_{2}=\ldots=n_{a}\) 时等号成立，即乘积最大。假设这一等分的长度为 \(x\)，即 \(n = ax\)，则乘积为 \(x^a\)。由于 \(n\) 为常数，因此我们有： \[ x^{a}=x^{\frac{n}{x}}=(x^{\frac{1}{x}})^{n} \] 我们只需要求出 \(y = x^{\frac 1 x}\) 的极大值即可，对其求导数可得到： \[ {y}'=\frac{1-\ln x}{x^{2}} x^{\frac{1}{x}} \] 因此当取得极值时 \(x_{0}=e \approx 2.7\)，易知此为极大值点。

由于切分长度必须为整数，所以取 \(x=2\) 或 \(x=3\)，经验证： \[ \begin{array}{l} y(3)=3^{1 / 3} \approx 1.44 \\ y(2)=2^{1 / 2} \approx 1.41 \end{array} \] 因此 \(x = 3\) 时，乘积最大。

而实际上，不可能所有的长度都能被 3 整除，但是尽可能的以 3 将绳子分割可以逼近理想中的最大值。因此，我们使用如下的贪婪算法：

  • 当 \(n \le 3\) 时，按题目要求必须切分，因此返回 \(n - 1\)；
  • 当 \(n > 3\) 时，把绳子尽可能地切为多个长度为 3 的片段，如果最后一段长度为 2，则保留，如果最后一段长度为 1，则把一份 \(3 + 1\) 替换为 \(2 + 2\)，因为 \(2 \times 2 > 3 \times 1\)。

基于上述方法的 python 实现如下：

class Solution:
    def cuttingRope(self, n: int) -> int:
        if n <= 3: return n - 1
        a, b = n // 3, n % 3
        if b == 0: return int(math.pow(3, a)) # 默认返回为浮点型，需要取整
        if b == 1: return int(math.pow(3, a - 1) * 4)
        return int(math.pow(3, a) * 2)

该方法的时间复杂度和空间复杂度均为 \(O(1)\)。注意： python 中 math.pow() 的求幂时间复杂度为 \(O(1)\)，* 和 pow()的时间复杂度为 \(O(\log a)\)。

剪绳子 II

此外，LeetCode 上还给出了此题的变式，添加了大数越界情况下的求余问题。答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，需返回 1。这种情况下如果采用动态规划算法，可能会导致超时，因此考虑使用贪婪算法。

在求余操作时需要注意，不能在最后一步再取余，因为最后的值可能已经超出范围，而应该在贪婪算法的每一步中进行求余，以保证不会越界。这里使用了快速幂求余算法，其时间复杂度为对数级别。这里对快速幂求余的原理进行简单的说明，首先给出两条求余相关的定理： \[ \begin{aligned} (ab) \odot c &=[(a \odot c)(b \odot c)] \odot c \\ a^b \odot c &= (a \odot c)^b \odot c \end{aligned} \] 基于上述两条定理，对于 \(a^{b} \odot c\)，我们可以推导出： \[ a^{b} \odot c =\left\{\begin{array}{ll} \left(a^{2} \odot c\right)^{b/2} \odot c & , b \text { 为偶数 } \\ {\left[(a \odot c)\left(a^{b-1} \odot c\right)\right] \odot c=\left[a\left(a^{2} \odot c\right)^{b / / 2}\right] \odot c} & , b \text { 为奇数 } \end{array}\right. \] 因此，我们可以通过循环将幂不断地减小直到变成 1，而底数则一直用原底数的平方求余替换即可。通过这种方法，我们可以得到较低的时间复杂度（二分），同时保证不会越界。快速幂求余的单独 java 实现如下：

int PowerMod(int a, int b, int c)
{
    int ans = 1;
    a = a % c; // 一般情况下先求一次余，不影响结果
    while (b > 0) {
        if (b % 2 == 1) ans = (ans * a) % c; // 最后一定会有一次奇数，也可以使用位运算 b & 1
        b /= 2; // 每次将 b 二分缩小，也可以使用位运算 b >>= 1
        a = (a * a) % c; // 不论奇偶都要更新
    }
    return ans;
}

上述实现中，当 b 为奇数时，需要额外地乘上 \(a \odot c\)，再循环下去，注意这里 ans 的初始值为 1，即在整个循环过程中 ans 只累积奇数情况下多出的部分，只有当 \(b = 1\) 时，才会将最终得到的底数计入（这里不太好理解，我想了很久才明白）。

基于快速幂求余，我们可以得到本题的解法：

class Solution {
    public int cuttingRope(int n) {
        if(n <= 3) return n - 1;
        int b = n % 3, p = 1000000007;
        long rem = 1, x = 3; // 使用 long 类型防止越界
        for (int a = n / 3 - 1; a > 0; a /= 2) { // 留一个 3 最后处理
            if (a % 2 == 1) rem = (rem * x) % p; // 使用快速幂求余
            x = (x * x) % p;
        }
        if (b == 0) return (int)(rem * 3 % p);
        if (b == 1) return (int)(rem * 4 % p);
        return (int)(rem * 6 % p);
    }
}

该方法的空间复杂度为 \(O(1)\)，时间复杂度与快速幂求余的复杂度相关，为 \(O(\log a)\)。