这道题不难。base只有2和3(拆开的结果比本身小，不需要拆开，所以是base)，超过4的数字一定可以拆开计算成更大的数字。
public class Solution {
public int integerBreak(int n) {
int base[] = {2,3};
if(n < 3) return 1;
int dp[] = new int[n+1];
dp[1] = 1; dp[2] = 1; dp[3] = 2;
for(int i=4; i<=n; i++) {
int max_tmp = 0;
for(int x : base) {
int max_curr = (i-x) <= 3 ? x*(i-x) : x*dp[i-x];
max_tmp = Math.max(max_curr, max_tmp);
}
dp[i] = max_tmp;
}
return dp[n];
}
}
网友评论