整数拆分
dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。
确定递推公式
可以想 dp[i]最大乘积是怎么得到的呢？
其实可以从1遍历j，然后有两种渠道得到dp[i].
一个是j * (i - j) 直接相乘。
一个是j * dp[i - j]，相当于是拆分(i - j)，对这个拆分不理解的话，可以回想dp数组的定义。
也可以这么理解，j * (i - j) 是单纯的把整数拆分为两个数相乘，而j * dp[i - j]是拆分成两个以及两个以上的个数相乘。
所以递推公式：dp[i] = max({dp[i], (i - j) * j, dp[i - j] * j});
那么在取最大值的时候，为什么还要比较dp[i]呢？
因为在递推公式推导的过程中，每次计算dp[i]，取最大的而已。
class Solution { public: int integerBreak(int n) { vector<int> dp(n+1,0); dp[2] = 1 ; for(int i=3 ; i<=n;i++) { //计算i的分割点，j从1开始分割到i-1 for(int j=1 ; j<i ;j++) { //找到最大乘积的时候 dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j)); cout<<"i:"<<i<<" dp:"<<dp[i]<<endl; } } return dp[n]; } };
二刷
class Solution { public: int integerBreak(int n) { if(n<=2) return 1; vector<int> dp(n+1,0); dp[1] = 1; dp[2] = 1; for(int i=3 ; i<=n ; i++) { int maxNum = 0; for(int j=1 ; j<i ;j++) { maxNum = max(maxNum ,max( dp[j]*(i-j) , j*(i-j))); } dp[i] = maxNum; // cout<<i<<' '<<dp[i]<<endl; } return dp[n]; } };
