class Solution {
public:
int integerBreak(int n) {
std::vector<int> dp(n+1);
dp[0]=0, dp[1]=0,dp[2]=1;
//i 4
//j 1 2 3 j<i优化成j<=i/2
//i-j 3 2 1
for (int i=3; i<=n;i++)
for (int j=1;j<=i/2;j++)
// 等价dp[i]=std::max({j*dp[i-j], j*(i-j),dp[i]});
dp[i] = std::max(dp[i],std::max(j*dp[i-j], j*(i-j)));
return dp[n];
}
};