[数据结构与算法]Leetcode 343. 整数拆分(动规) 记录反思

做的第一道中等递归,还是有一点难度的

第一步:
递归首先要确定递归数组的功能
dp[i] : 数字i的最大整数拆分值

第二步:
写出递推表达式,我一般习惯写出几个值然后找推导关系
这个题目的dp[0] 和 dp[1] 理论上是没有意义的,所以从dp[2] 开始

dp[2] = 1 => 1x1
dp[3] = 2 => 1x2

dp[4] 可以是 dp[3]* 1 或者 dp[2] * 2 或者是 2+2 中的最大值
dp[3] *1 就相当于 1+2+1 dp[2]*2 就相当于 1+1+2

所以对于dp[i] 可以推导出 dp[i] = max(dp[i-j] * j ,(i-j) * j)

所以可以写出代码

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

然后结果不对.
然后反复观察才发现 每次循环的dp[i] 都是会变得 ,可能之前是最大值,然后后面算出来的就又小了,所以要保留最大值,最后代码改成

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

过啦