1.原题地址：
343. 整数拆分 - 力扣（LeetCode） (leetcode-cn.com)
2.题目描述：给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:
输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。
示例2：
输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: n 不小于 2 且不大于 58。
3.分析
动态规划三部曲：
(1) 首先定义数组，dp[i]，i代表需要被拆分的整数，dp[i]代表整数i被拆分后得到的最大乘积
(2)分析递推公式
对于整数 i ，i >2，假设 i 被拆分成m1+m2+...+mk得到的乘积最大，可以分析得知 1<k<n+1
i = m1+m2+...+mk= （m1+m2+...+mk-1）+mk
对于数字i，至少要被拆分成两个数字，记作 i = (i -j) + j，
对于j = mk，不再被拆
对于( i-j ) = m1+m2+...+mk-1，如果被拆则乘积为 i*dp[i-j]，如果不被拆则乘积为 i*j
所以最大乘积为 max ( i*dp[i-j] , i*j )
(3) 边界
dp[0] = 0，dp[1] = 0
4.完整代码
1 class Solution { 2 public: 3 int Max(int num1,int num2) 4 { 5 return num1>num2 ? num1:num2; 6 } 7 int Max(int num1,int num2,int num3) 8 { 9 return num3>Max(num1,num2) ? num3:Max(num1,num2); 10 } 11 int integerBreak(int n) { 12 if(n==2) 13 return 1; 14 int *dp = new int[n+1]; 15 dp[0] = 0; 16 dp[1] = 0; 17 dp[2] = 1; 18 for(unsigned i=3;i<n+1;++i) 19 { 20 dp[i] = i-1; 21 for(unsigned j=1;j<i;++j) 22 { 23 dp[i] = Max(dp[i],dp[i-j]*j,(i-j)*j); 24 } 25 } 26 int result = dp[n]; 27 delete []dp; 28 return result; 29 } 30 };