【LeetCode343】剪绳子（动态规划）

（1）确定状态
dp[i]是将正整数i拆成2个及其以上的正整数后，求所有数的乘积值。

（2）状态转移方程
当 i≥2 时，假设对正整数 i 拆分出的第一个正整数是 j（1≤j 1）将 i 拆分成 j 和 i−j 的和，且 i−j 不再拆分成多个正整数，此时的乘积是 j×(i−j)；
2）将 i 拆分成 j 和 i−j 的和，且 i−j 继续拆分成多个正整数，此时的乘积是 j×dp[i−j]。
因此，当 j 固定时，有 d p [ i ] = m a x ( j × ( i − j ) , j × d p [ i − j ] ) dp[i]=max(j×(i−j),j×dp[i−j]) dp[i]=max(j×(i−j),j×dp[i−j])由于 j 的取值范围是 1 到 i−1，需要遍历所有的 j 得到 dp[i] 的最大值，因此可以得到状态转移方程如下： d p [ i ] = max ⁡ 1 ≤ j < i ( j × ( i − j ) , j × d p [ i − j ] ) d p[i]=max _{1 leq j

最终得到 dp[n] 的值即为将正整数 n 拆分成至少两个正整数的和之后，这些正整数的最大乘积。

（3）边界+初始条件
边界条件： 0 不是正整数，1 是最小的正整数，0 和 1 都不能拆分，因此 dp[0]=dp[1]=0。

（4）计算顺序
从小到大。

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