题解 | #剪绳子#

class Solution {
public:
    int cutRope(int number) {
        vector<int> dp(number + 1, 0);
        dp[2] = 1;
        dp[3] = 2;
        dp[4] = 4;
        dp[5] = 6;
        dp[6] = 9;
        if(number <= 6) 
            return dp[number];
        for(int i = 7; i <= number; i++)
            for(int j = 2; j <=i-5; j++)
                dp[i] = max(dp[i], j * dp[i - j]);
        return dp[number];
    }
};

这道DP题真的藏得很深，如果按照题目的说法绳子至少被分成两段官方的解法完全就是错的！

DP算法的两个阶段：初始状态和状态转移，隐藏了一个条件，就是初始状态必须要能够转移到后面的状态！

我们看这道题：

DP[2] = 1;

DP[3] = 2;

DP[4] = 4;

也就是说，对于绳子长度小于等于4的，再分割就是乘积越来越小，也就是说DP[3]及之前的状态无法转移到之后

举个例子DP[6] = max(DP[6], 2*DP[4])

DP[6] = j*DP[i-j]永远都无法成立，如果没有这个DP[6]的初始状态，那么就无法再进行状态转移了

那么什么时候状态转移可以成功呢？

DP[7] = 3*DP[4] = 2*2*3 = 12

我们发现DP[6]是状态转移的真正开始的位置，是一个状态转移的极限

因此我们的状态转移需要从DP[7]开始，或者将DP[7]之前的状态全部初始化！（注意这里虽然用的是或者，实际上这两种方法的本质和结果都是一样的）

有了以上的推论，另外一个细节就是我们的j可以从2开始，因为分出1米出去乘积肯定是更小的，当然从后面官方的数学解法我们可以已知分出去的j>=3才有意义，当然这是后话了。另外，j的右边界也可以同样缩小到DP[j]>j（相等的情况实际上在左边界已经包含了，即j=4，此时DP[4]=4），所以我们可以将右边界缩小到DP[5]，也就是j <=i-5。