剑指 Offer 14- I. 剪绳子

思路

方法一：动态规划

从题目中可以看出，有最优子结构，可以联想到动态规划，其递归树如下：

可以看出，具有很多重叠子问题。

 1 /*记忆化搜索代码*/
 2 class Solution {
 3 private:
 4     // 记忆化搜索，自顶向下
 5     // memo[n]表示分割n获得的乘积最大值
 6     vector<int> memo;
 7     int max3(int a, int b, int c) {
 8         return max(a, max(b,c));
 9     }
10     int breakInteger(int n) {
11         if(n == 1)
12             return 1;
13 
14         if(memo[n] != -1)
15             return memo[n];
16 
17         int res = -1;
18         for(int i = 1; i < n; ++i) {
19             res = max3(res, i*(n-i), i * breakInteger(n-i));
20         }
21         memo[n] = res;
22         return memo[n];
23         
24     }
25 public:
26     int integerBreak(int n) {
27         memo = vector<int>(n+1, -1);
28         return breakInteger(n);
29     }
30 };
31 
32 /*动态规划代码*/
33 class Solution {
34 private:
35     // 动态规划，自底向上
36     // 求三个数中的最大值
37     int max3(int a, int b, int c) {
38         return max(a, max(b,c));
39     }
40     
41 public:
42     int integerBreak(int n) {
43         vector<int> memo(n+1, -1);
44         // memo[i]表示分割i获得的乘积最大值
45         // 题目中说了n>=2，所以这里不能写memo[3]=2,否则当输入的n是2时会越界
46         memo[1] = 1;
47         memo[2] = 1;
48         for(int i = 3; i <= n; ++i) {
49             for(int j = 1; j < i; ++j) {
50                 memo[i] = max3(memo[i], j*(i-j), j*memo[i-j]);
51             }
52         }
53         return memo[n];
54     }
55 };

复杂度分析

记忆化搜索：

时间复杂度：O(n²)，因为breakInteger递归函数中有一个n次循环，每个memo[i]的值只会被计算一次，不会重复递归计算相同的memo[i] (因为相同的直接返回了)，所以时间复杂度为O(n²)

空间复杂度：O(n)

动态规划：

时间复杂度：O(n²)

空间复杂度：O(n)

方法二：数学

以下证明来自：《剑指offer(第2版)》，面试题14- I. 剪绳子（数学推导 / 贪心思想，清晰图解）

更详细的数学证明见：力扣官方题解 - 整数拆分

 1 class Solution {
 2 public:
 3     int cuttingRope(int n) {
 4         if(n <= 3)  
 5             return n-1;
 6         int res = 1;
 7         while(n > 4)
 8         {
 9             n    = n - 3;           //尽可能地多剪长度为3的绳子
10             res  = res * 3;         
11         }
12         return res * n;
13     }
14 };

参考

力扣官方题解 - 整数拆分

c++ dp和贪心 -z

面试题14- I. 剪绳子（数学推导 / 贪心思想，清晰图解）