剑指offer 面试题14- I. 剪绳子（中）& LeetCode 343.整数拆分（中）

动态规划问题的建模直觉如何培养？

Tag

动态规划、贪心算法

参考连接

面试题14- II. 剪绳子 II（数学推导 / 贪心思想 + 快速幂求余，清晰图解）

本题考点

  1. 考查应聘者的抽象建模能力。应聘者需要把一个具体的场景抽象成一个能够用动态规划或者贪婪算法解决的模型。
  2. 考查应聘者对动态规划和贪心算法的理解。能够灵活运用动态规划解决问题的关键是具备从上到下分析问题、从下到上解决问题的能力，而灵活运用贪婪算法则需要扎实的数学基本功。

题目

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

示例 1： 

1
2
3
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
示例 2: 
1
2
3
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
提示：2 <= n <= 58

直觉

动态规划

这个问题的目标是求剪出的各段绳子长度的乘积最大值，也就是求一个问题的最优解一—这是可以应用动态规划求解的问题的第一个特点。

我们把长度为n的绳子剪成若干段后得到的乘积最大值定义为函数 \(f(n)\)。假设我们把第一刀剪在长度为\(i(0<i<n)\) 位置，于是把绳子剪成了长度分别为 \(i\) 和 \(n-i\) 的两段。我们要想得到整个问题的最优解 \(f(n)\)，那么要同样用最优化的方法把长度为 \(i\) 和 \(n-i\) 的两段分别剪成若干段，使得它们各自剪出的每段绳子的长度乘积最大。也就是说整体问题的最优解是依赖各个子问题的最优解——这是可以应用动态规划求解的问题的第二个特点。

我们把大问题分解成若干个小问题，这些小问题之间还有相互重叠的更小的子问题——这是可以应用动态规划求解的问题的第三个特点。

用从下往上的顺序先计算小问题的最优解并存储下来，再以此为基础求取大问题的最优解。从上往下分析问题，从下往上求解问题，这是可以应用动态规划求解的问题的第四个特点。

从上往下分析问题

首先定义函数 \(f(n)\) 为把长度为n的绳子剪成若干段后各段长度乘积的最大值。在剪第一刀的时候，我们有 \(n-1\) 种可能的选择，也就是剪出来的第一段绳子的可能长度分别为 \(1, 2, n-1\)。因此 \(f(n)=max((i) \times(n-i))\)，其中 \(0<i<n\)。

从下往上求解问题

这是一个从上至下的递归公式。由于递归会有很多重复的子问题，从而有大量不必要的重复计算。一个更好的办法是按照从下而上的顺序计算，也就是说我们先得到 \(f(2)\)、\(f(3)\)，再得到 \(f(4)\)、\(f(5)\)，直到得到 \(f(n)\)。当绳子的长度为2时，只可能剪成长度都为1的两段，因此 \(f(2)=1\)。当绳子的长度为3时，可能把绳子剪成长度分别为1和2的两段或者长度都为1的三段，由于 \(1 \times 2>1 \times 1 \times 1\)，因此 \(f(3)=2\)。

贪心算法

如果我们按照如下的策略来剪绳子，则得到的各段绳子的长度的乘利子最大：当\(n\geq5\)时，我们尽可能多地剪长度为3的绳子；当剩下的绳子度为4时，把绳子剪成两段长度为2的绳子。

换而言之，切分规则为： 最优： \(3 \times 3\) 。把绳子尽可能切为多个长度为 3 的片段，留下的最后一段绳子的长度可能为 0, 1, 2 三种情况。 次优： \(2 \times 2\) 。若最后一段绳子长度为 2 ；则保留，不再拆为 1+1 。 最差： \(1 \times 1\) 。若最后一段绳子长度为 1 ；则应把一份 3 + 1 替换为 2 + 2，因为 \(2 \times 2 > 3 \times 1\)。

接下来我们证明这种思路的正确性。首先，当 \(n\geq5\) 的时候，我们可以证明 \(2(n-2)>n\) 并且 \(3(n-3)>n\)。也就是说，当绳子剩下的长度大于或者等于5的时候，我们就把它剪成长度为3或者2的绳子段。另外，当 \(n\geq5\) 时，\(3(n-3)\geq2(n-2)\)，因此我们应该尽可能地多剪长度为3的绳子段。 前面证明的前提是 \(n\geq5\)。那么当绳子的长度为4呢？在长度为4的绳子上剪一刀，有两种可能的结果：剪成长度分别为1和3的两根绳子，或者两根长度都为2的绳子。注意到 \(2×2>1×3\)，同时 \(2×2=4\)，也就是说，当绳子长度为4时其实没有必要剪，只是题目的要求是至少要剪一刀。

代码

  • 动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import unittest
from typing import List

# Dynamic Programing
class Solution:
    def cuttingRope(self, n: int) -> int:
        """
        :param n(2 <= n <= 58): int
        """
        dp = [0, 1, 2, 3]
        if n == 0: return -1
        if n < 4:  return dp[n-1]
        _max = 0
        for i in range(4, n+1):
            dp.append(0)
            _max = 0
            # 在剪第一刀的时候，我们有 n-1 种可能的选择。
            # 也就是剪出来的第一段绳子的可能长度分别为 1, 2, n-1。
            # 因此 f(n)=max((i)*(n-i))，其中 0<i<n。
            # 一般来说，要遍历1到n，但是遍历1到n//2即可计算得到f(n)=max((i)*(n-i))。
            for j in range(1, (i//2)+1):
                product = dp[j] * dp[i-j]
                if _max < product:
                    _max = product
                dp[i] = _max
        _max = dp[n]

        return _max

class TestSolution(unittest.TestCase):
    def setUp(self):
        self.test_class = Solution()

    def test_solution(self):
        inputs = [
            6, 10,  # 功能测试
            2, 52,  # 边界测试
            0,      # 特殊样例
        ]
        answers = [9, 36, 1, 172186884, -1]
        res = []
        for i in range(len(inputs)):
            res.append(self.test_class.cuttingRope(inputs[i]))
        self.assertEqual(res, answers)
 
    def tearDown(self):
        del self.test_class


if __name__ == "__main__":
    unittest.main()

时间复杂度为 \(O(n^2)\)， 空间复杂度为 \(O(n)\)。

  • 贪心算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Greedy Algorithm
class Solution:
    def cuttingRope(self, n: int) -> int:
        """
        :param n(2 <= n <= 58): int
        :return int:
        """
        dp = [0, 1, 2, 3]
        if n == 0: return -1
        if n < 4:  return dp[n-1]

        # 计算均分多段，每段长度为3，可以分出多少段。
        timeOf3 = n // 3

        # 如果最后剩下1，则timeOf3减1 保留一个2*2。
        if n - timeOf3 * 3 == 1:
            timeOf3 -= 1

        # 计算均分多段，每段长度为3之后，再均分多段，每段长度为2，可以分出多少段。
        timeOf2 = (n - timeOf3 * 3) // 2

        return (3**timeOf3) * (2**timeOf2)

时间复杂度为 \(O(1)\)， 空间复杂度为 \(O(1)\)。

举一反三

题目

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

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

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

示例 2:

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

提示：2 <= n <= 1000

解析

与上面一道题不同之处在于，本题目涉及 “大数越界情况下的求余问题” 。n 的大小允许超过52，最终的结果可能就会大于int32允许的范围(\(-2147483648 \rightarrow 2147483647\))，也就是我们常说的溢出。

大数越界情况下的求余问题

大数越界： 当 a 增大时，最后返回的 \(3^a\) 大小以指数级别增长，可能超出 int32 甚至 int64 的取值范围，导致返回值错误。 大数求余问题： 在仅使用 int32 类型存储的前提下，正确计算 \(x^a\) 对 p 求余（即 \(x^a \odot p\)）的值。 解决方案： 循环求余 、 快速幂求余 ，其中后者的时间复杂度更低，两种方法均基于以下求余运算规则推出： \[ (xy) \odot p = [(x \odot p)(y \odot p)] \odot p \]

循环求余

根据求余运算性质推出（∵ 本题中 \(x<p\)，∴ \(x \odot p = x\) ）： \[ x^a \odot p = [(x ^{a-1} \odot p)(x \odot p)] \odot p=[(x ^{a-1} \odot p)x] \odot p \] 解析： 利用此公式，可通过循环操作依次求 \(x^1, x^2, ..., x^{a-1}, x^a\)对 \(p\) 的余数，保证每轮中间值 rem 都在 int32 取值范围中。封装方法代码如下所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 求 (x^a) % p —— 循环求余法
# 在rem的基础上累乘，rem默认是1
def remainder(self, rem, x, a, p):
    """ Circular remainder
    :param rem: int(basic value)
    :param x: int(power number)
    :param a: int(calculation times)
    :param p: int(dividend)
    :return int:
    """
    # rem = 1
    for _ in range(a):
        rem = (rem * x) % p
    return rem

时间复杂度 \(O(N)\) ： 其中 \(N=a\) ，即循环的线性复杂度。

快速幂求余

根据求余运算性质可推出： \[ x^a \odot p = (x^2)^{a/2} \odot p = (x^2 \odot p)^{a / 2} \odot p \] 当 a 为奇数时 a/2 不是整数，因此分为以下两种情况（ ''//'' 代表向下取整的除法）：

\[ {x^a \odot p = } \begin{cases} (x^2 \odot p)^{a // 2} \odot p & \text{, $a$ 为偶数} \\ {[(x \odot p)(x ^{a-1} \odot p)] \odot p = [x(x^2 \odot p)^{a//2}] \odot p} & \text{, $a$ 为奇数} \\ \end{cases} \]

解析： 利用以上公式，可通过循环操作每次把指数 a 问题降低至指数 a//2问题，只需循环 \(log_2(N)\) 次，因此可将复杂度降低至对数级别。封装方法代码如下所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 求 (x^a) % p —— 快速幂求余
# 在rem的基础上累乘，rem默认是1
def remainder(self, rem, x, a, p):
    """fast power remainder
    :param rem: int(basic value)
    :param x: int(power number)
    :param a: int(calculation times)
    :param p: int(dividend)
    :return int:
    """
    # rem = 1
    while a > 0:
        if a % 2:  rem = (rem * x) % p
        x = x ** 2 % p
        a //= 2
    return rem

时间复杂度 \(O(\log_2 N)\) ： 其中 \(N=a\) ，二分法为对数级别复杂度，每轮仅有求整、求余、次方运算。 求整和求余运算：资料提到不超过机器数的整数可以看作是 \(O(1)\) ； 幂运算：查阅资料，提到浮点取幂为 \(O(1)\) 。 空间复杂度 \(O(1)\) ： 变量 a, b, p, x, rem 使用常数大小额外空间。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# Greedy Algorithm
class Solution:
    # 求 (x^a) % p —— 循环求余法
    def remainder(self, rem, x, a, p):
        # rem = 1
        for _ in range(a):
            rem = (rem * x) % p
        return rem

    # # 求 (x^a) % p —— 快速幂求余
    # def remainder(self, rem, x, a, p):
    #     # rem = 1
    #     while a > 0:
    #         if a % 2:  rem = (rem * x) % p
    #         x = x ** 2 % p
    #         a //= 2
    #     return rem

    def cuttingRope(self, n: int) -> int:
        """
        :param n(2 <= n <= 58): int
        :return int:
        """
        dp = [0, 1, 2, 3]
        if n == 0: return -1
        if n < 4:  return dp[n-1]
        MODULES = 1000000007

        timeOf3 = n // 3
        # 如果最后剩下 4 timeOf3就减1 保留一个2*2
        if n - timeOf3 * 3 == 1:
            timeOf3 -= 1

        # 当n<5时，最好的拆段方法是2*2。
        timeOf2 = (n - timeOf3 * 3) // 2
        
        # 最终计算时，要做求余，第一次传入的rem是1
        tmp = self.remainder(1, 3, timeOf3, MODULES)

        # 第二次在第一次的结果上继续累乘，传入的rem是tmp
        return self.remainder(tmp, 2, timeOf2, MODULES)