十年旧约江南梦
独听寒山半夜钟
C++，动态规划，贪心。。。。最重要的是这是道数学题！！！
很多博客一上来就是dp，贪心，也不解释为什么这样是最优解，一言难尽，其实这就是道数学题，明白其中的数学思想，就知道怎么用dp和贪心解了。
动态规划
首先，我们会发现这么一个规律（假设绳子长 \(l\) 只能被剪成两段 \(x\) 和 \(y\) ）：
- 如果 \(l < 4\)，会发现无论怎么组合，都会有\(l > xy\)
- 比如 \(3 > 2 * 1 \)
- 比如 \(2 > 1 * 1 \)
- 而如果 \(l \ge 4 \)，会发现无论怎么组合，都会存在 \(l \geq xy \)
- 比如 \(4 = 2 * 2 \)
- 比如 \(5 < 2 * 3 \)
也就是说当一个数大于4的时候，我们就应该把它分解，来得到更大的乘积。
所以，可以整理出如下公式：
\[f(n) = max\{f(1)f(n-1), f(2)f(n-2)....f(n-1)f(1)\}\]同样的，如果对应的子项\(f(i) \)，其中 \(i > 4 \)，也是可以分解的。所以就变成了递归分解了，既然是递归，就要想到能不能用额外空间去记录递归的中间结果呢？
woc！！！这不就是DP嘛！！！
所以就能写出下面的代码了：
class Solution {
public:
int cutRope(int number) {
int *dp = new int[number + 1];
dp[1] = 1;
dp[2] = 1;
dp[3] = 2;
dp[4] = 4;
for (int i = 5; i <= number; i++) {
for (int j = 1; j <= i / 2; j++) {
dp[i] = max(dp[i], dp[j] * dp[i-j]);
dp[i] = max(dp[i], j * dp[i-j]);
dp[i] = max(dp[i], (i - j) * dp[j]);
dp[i] = max(dp[i], (i - j) * j);
}
}
delete[] dp;
return dp[number];
}
};
贪心
同样也是数学问题，基于前面的数学结论：当一个数大于4的时候，我们就应该把它分解，来得到更大的乘积。
我们会发现，大于等于4的数，一定能够被分解成若干个2和3的和。那多点2好呢，还是多点3好呢？
因为做人不能太2，还是3吧。
好吧其实有个结论就是：
\[3(n-3) \ge 2(n-2)\]化简就是：
\[3n-9 \ge 2n-4\] \[n >= 5\]也就是$n \ge 5$，则有$3(n-3) \ge 2(n-2)$。
所以就是尽量3多一点好了，但是不能出现1，出现1的话，3就没用了呀。
所以就有了贪心的答案：
class Solution {
public:
int cutRope(int number) {
if (number < 2)
return 0;
else if (number < 4)
return number -1;
int cnt_3 = number / 3;
if (number % 3 == 1)
return (int) pow(3, cnt_3 - 1) * 4;
else
return (int) pow(3, cnt_3) * 2;
}
};
