割舍绳子/整数分割

当 i > 2时，假设对正整数i拆分出的第一个正整数时j（1<=j<i - 1,因为从2开始）那么有以下两种方案：

• 将i拆分成j和i-j的和，且i-j不能再拆分成多个正整数，此时的乘积是j*（i-j）
• 将i拆分成j和（i-j）的和，且i-j可以继续拆分成多个正整数，此时的成及是j*dp[i-j]
• dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));只是取dp[i]的最大值

class Solution {
    
public:
    int integerBreak(int n) {
    
        vector<int> dp(n + 1);
        dp[2] = 1;
        for (int i = 3; i <= n ; i++) {
    
            for (int j = 1; j < i - 1; j++) {
    
                dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
            }
        }
        return dp[n];
    }
};