leetcode343. 整数拆分

1.题目描述：

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

 2.递归解法：

首先寻找不同n值拆分后乘积最大值之间的关系，不好找，借用97wgl答主的图来解释如下：

F(n)中拆出1~n-1，比如拆出i，剩余n-i，剩余n-i的拆法要使得拆后的乘积最大则拆法即为F(n - 1)的拆法，一个循环横向拆出一个数，取F(n) = Math.max(i * F(n - i))，当然横向遍历中会有重复的计算结果，其中如果出现n-i > F(n - i)的情况，停止继续纵向拆分，两个数的乘积最大。 这就是前后的关系，也是动态规划递推公式的由来。代码如下，类似回溯的代码，超时。

class Solution {
    public int integerBreak(int n) {
        if (n == 2) return 1;
        int max = Integer.MIN_VALUE;
        int temp = 0;
        for (int i = 1; i < n; i++) {
            temp = Math.max(i * (n - i), i * integerBreak(n - i));
            max = Math.max(temp, max); 
        }
        return max;
    }
}

看上图也能发现，递归中重复计算了多次F(n - 2)，F(n - 3)等等，记忆化保存已经算过的结果，再次遇到直接取即可。 

class Solution {
    private int[] arr;
    public int integerBreak(int n) {
        if (n == 2) return 1;
        arr = new int[n];
        helper(n);
        return arr[n - 1];
    }

    public int helper(int n) {
        if (n == 2) return 1;
        if (arr[n - 1] != 0) return arr[n - 1];
        int max = Integer.MIN_VALUE;
        for (int i = 1; i < n; i++) {
            int temp = Math.max(i * (n - i), i * helper(n - i));
            max = Math.max(max, temp);
        }
        arr[n - 1] = max;
        return max;
    }
}

3.动态规划：

dp[i]依赖于先前的dp数组值，通过循环遍历得到dp[i]的最大值。

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