Leetcode 343. 整数拆分 java题解
https://leetcode.cn/problems/integer-break/
我想不到
class Solution {
//int max=0;
public int integerBreak(int n) {
int[] dp=new int[n+1];//dp[n]：n拆分后的最大乘积
dp[2]=1;//2只能被拆成2个，1+1，1*1=1
for(int i=3;i<=n;i++){
for(int j=1;j<i;j++){
//j是从1开始遍历，拆分j的情况.所以j不需要再拆
dp[i]=Math.max(Math.max(dp[i-j]*j,(i-j)*j),dp[i]);
//在递推公式推导的过程中，每次计算dp[i]，取最大的
}
}
return dp[n];//返回结果
}
}
//j * (i - j) 是单纯的把整数拆分为两个数相乘
//而j * dp[i - j]是拆分成两个以及两个以上的个数相乘
//dp[i] 是依靠 dp[i - j]的状态，所以遍历i一定是从前向后遍历，先有dp[i - j]再有dp[i]