DP进阶之路——整数拆分

343.?整数拆分

给定一个正整数?n?，将其拆分为?k?个?正整数?的和（?k >= 2?），并使这些整数的乘积最大化。

返回?你可以获得的最大乘积?。

示例 1:

输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例?2:

输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 ×?3 ×?4 = 36。

这种题目，我们第一眼肯定都是直接原地暴力破解，直接利用回溯去试一下?

?

class Solution {
    int max;
    int sum = 1;
    public int integerBreak(int n) {
        if(n == 2)  return 1;
        if(n == 3)  return 2;
        max = Integer.MIN_VALUE;
        dfs(n);
       
        return max;
    }

    void dfs(int n){
        if(n<0) return;
        if(n == 0){
            max=Math.max(max,sum);
            return;
        }
        for(int i =1;i<= n && n>0;i++){
            sum = sum*i;
            dfs(n-i);
            sum = sum/i;
        }
    }
}

结果很遗憾，经典时间超限。所以我们可以来进行优化一下。

可以通过记录我们已经运行过了乘积，免去多余的运行（可以说是剪枝）?

?

class Solution {
    public int integerBreak(int n) {
        if (n == 2) return 1;    
        if (n == 3) return 2;    //这里是两种的特殊情况
        return dfs(n, new int[n + 1]);
    }

    private int dfs(int n, int[] memo) {    //这里的memo数组就是用来记录运行过的
        if (n == 2) return 2;
        if (memo[n] > 0) return memo[n];    //如果大于0，就是已经被记录了，直接返回就行
        
        int max = 0;
        for (int i = 1; i < n; i++) {
            max = Math.max(max, i * Math.max(n - i, dfs(n - i, memo)));
        }
        memo[n] = max;
        return max;
    }
}

一运行，我们就发现我们过了。然后，我们还可以通过递推优化，就是动态规划。

我们先要确定：dp[i] 是什么，其实是n == i时候的拆分出来的整数的最大乘积。

提出一个问题，这个怎么求出来呢？

?

?

我们其实可以有两种方式获得dp[i]

第一种：i*(n-i)? ? ? ? 这是两个数直接求

第二种：i*(dp[n-i])? ? ? ? 这里是和多个数求

class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n+1];
        dp[0] = dp[1] = 0;
        for(int i =2;i<=n;i++){
            int temp = 0;
            for(int j = 1;j<= i;j++){
                temp = Math.max(Math.max(j*(i-j),j*dp[i-j]),temp);
    //这里是比较两种求值的所有情况，最后获得最大值
            }
            dp[i] = temp;
        }
        return dp[n];
    }
}