力扣—DP：整数拆分

原题连接：

343. 整数拆分 - 力扣（LeetCode） (leetcode-cn.com)

给定一个正整数 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。

思考搞一下：

首先，我们来确定dp[i]的含义，原题中给出，需要求最大值，那么dp[i]便表示i的拆分整数最大积。

既然dp[i]为最大值了，那么推导一下递推公式，有两种方式获得dp[i]。一种是j*(i-j)，另外一种是j*dp[i-j]。

对于j*(i-j)我们不难理解，但是是不是总觉得少了点啥，题目中明明可以拆分出来好几项，为什么到这里只变成了两项？

其实我们不难理解，j*dp[i-j]就相当于将i拆分成了j和dp[i-j]，而这里的dp[i-j]也并不是一项，而是指的多项，也就是当i拆出来j之后剩下的(i-j)拆分后的最大值。

换一种说法就是，我们可以设i=j*x，j就是实实在在我们遍历的j，x其实就是相当于i-j后，将x进行拆分乘积的最大值。

比如10 = 3 + 3 + 4，3 × 3 × 4 = 36。这里i=10,j=3,x=（3*4）。x相当于i-j=7，7由拆分成3+4得到的最大值。

所以完整的递推公式也就是dp[i] = max(dp[i],max(j*(i-j),j*dp[i-j]))。

因为dp[i]依赖于dp[i-j]所以也就是从前往后遍历。

class Solution {
    int max(int a,int b){
        return a>b?a:b;
    }

    public int integerBreak(int n) {
        int[] dp = new int[n+1];
        dp[2] = 1;
        for(int i = 3;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];
    }
}