343. 整数拆分 (opens new window)

1.动规

分析：dp[n]表示将n拆分后得到的最大乘积。考虑递推公式时，如果只使用子问题的dp结果计算是不对的，比如乘数出现2的情况，注意子问题也是分成两种情况，拆分与不拆分。求解dp[n]时需要枚举乘数为i<n的所有情况，将多个乘积相乘看作是两个可拆分的乘数i与n-i相乘(相当于劈开两半，左右两半都存在继续劈与不劈两种选择)：

• i与n-i同时拆分：dp[n]=dp[i]*dp[n-i]
• 拆分i或者n-i：dp[n]=dp[i]*(n-i)
• 都不拆分：dp[n]=(i) * (n-i)

枚举时对于每个 i 取三者乘积的最大值进行更新。

PS:另一种枚举的思路是，遍历枚举“第一个拆分出来的数”，剩余部分只有两选择，继续拆分或者不拆分。无论是哪种都建立在“至少拆分成两个数”这一条件下。

class Solution {
    public int integerBreak(int n) {
        int[] dp=new int[n+1];
        dp[1]=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<i;j++){
                dp[i]=Math.max(dp[i],dp[j]*(i-j));
                dp[i]=Math.max(dp[i],dp[j]*dp[i-j]);
                dp[i]=Math.max(dp[i],j*(i-j));
            }
        }
        return dp[n];
    }
}