一.媒介
迩来不绝在了解动态规划，这是LeetCode上面的一道动规的题。
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。
二.思绪
说到动态规划，我认为最重要的就是确定自己的 dp数组 的寄义，其次就是 递推公式 了。
我们重新浏览一遍题，给定一个正整数 n ，须要将它分成多少个整数，返回最大的乘积。因此我们可以界说 dp 表现每个正整数拆分为多少个正整数所对应的最大乘积，若要确定 dp 的值，我们可以根据 dp 从前的元素举行运算从而得到最大的
dp 的值。
dp 的值是由两种方式来共同确定的。
第一，dp = dp[i - j] * j 此中 i 代表外层循环， j 代表内层循环，j 从 1 开始逐个求出 dp ，最后取最大值。
第二，dp = (i - j) * j，同上，也是取最大值。上面那种方式是将 i 分成了 n 个 (n > 2)。而这种方式是将 i 分成了n 个 (n = 2)。
实在到这里，递推公式大抵样式也就出来了:
dp = Math.max(dp, Math.max(dp[i - j] * j, (i - j) * j)) ，那么大概会有人问为什么还要比力一次 dp 呢？因为我们内层循环中一周后，会算出许多 dp ，我们只须要生存最大的 dp。
三.代码
class Solution { public int integerBreak(int n) { int[] dp = new int[n + 1]; //dp[2]对应的值应该是1，而dp[2]之前的元素在此题目中无现实意义，因此无需初始化 dp[2] = 1; for(int i = 3; i <= n; i++){ for(int j = 1; j <= i - j; j++){ dp = Math.max(dp, Math.max(dp[i - j] * j, j * (i - j))); } } return dp[n]; }}时间复杂度 O(n^2)
- 题外话
这道题用动态规划的话时间复杂度好像有点高，实在这道题可以用数学方法来写的，这里用到一个结论：当整数 n 尽大概地平分为 3时乘积最大。假如感爱好的同砚可以去证实一下。
class Solution { public int integerBreak(int n) { if(n <= 3) return n - 1; int a = n / 3, b = n % 3; //当 n 分刚好能分成多少个 3 时 if(b == 0) return (int)Math.pow(3, a); //当 n 尽大概分成 3 时，余出一个 1 if(b == 1) return (int)Math.pow(3, a - 1) * 4; //当 n 尽大概分成 3 时，余出一个 2 return (int)Math.pow(3, a) * 2; }}时间复杂度：O(1) |
