Leetcode343.整数拆分

这道题从拆分的逻辑可以尝试使用动态规划，但是说实话这道题很难想到递推公式。

根据Carl的动规五部曲：

1. 确立 dp 数组的含义：

数字 i 拆分后的最大乘积为 dp[i]

2. 明确递推公式：

dp[i]有两种途径得到，一种是只拆成两个数，一种是拆成多个数。分为这两种的原因是题目中规定了k>=2。

比如从 1 到 j 的遍历中，一种是 j * (i – j)，一种是 j * dp[i – j]，相当于是拆分了(i – j)。不拆分 j 的原因是，拆分 dp[i – j] 的情况中，已经天然的包含了拆分 j 的情况。

在遍历过程中，我们要取 (i – j) * j 和 dp[i – j] * j 中最大的。不难得出递推公式：dp[i] = max(dp[i], max((i – j) * j, dp[i – j] * j));

3. 初始化：

dp[0] 和 dp[1] 实际上是无法拆分的，且题目说明了给出的正整数 n >= 2，所以直接考虑 dp[2] = 1

4. 确定遍历顺序：

显然是从前向后遍历

5. 举例推导dp数组：

这里根据2、3、4、5，很容易就推出来 dp 数组的递推公式都符合

给出完整代码：

class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];  // 数字i拆分后的最大乘积为dp[i]
        dp[2] = 1;  // 初始化 2 的最大乘积是1
        for (int i = 3; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                // j * (i - j) 是单纯的把整数 i 拆分为两个数 也就是 i,i-j ，再相乘
                //而j * dp[i - j]是将 i 拆分成两个以及两个以上的个数,再相乘。
                dp[i] = Math.max(dp[i], Math.max(j*(i-j),j*dp[i-j]));
            }
        }
        return dp[n];
    }
}

总结一下，这道题实际上是对数学功底有要求的，递推公式也不好想，是一道需要多多品味的题目。