美团面试动态规划——整数拆分

dp[i]代表i这个数拆分后所能得到的最大乘积

class Solution { public: int integerBreak(int n) { vector<int> dp(n+1,0); dp[1]=1; for(int i=2;i<=n;i++) for(int j=1;j<i;j++) dp[i]=max(dp[i],max(dp[j],j)*(i-j)); return dp[n]; } };