题目链接
题目描述
实现代码
动态规划思想:记dp[i]表示数字i的拆分次数,我们最终要求的是dp[n],首先初始化条件:
- dp[0] = 0
- dp[1] = 1
然后编写状态转移方程:
dp[i] = max(dp[i-1] _1, dp[i-2] _2, … dp[i-i+1] * 1)
这里我们还需要考虑一点:即拆分成两个数的情况,所以状态转移方程除了上述的最大值外,还要取下列情况的最大值:
dp[i] = max((i-1) 1, (i-2) 2, … (i-i+1) * (i-1))
实现代码:
class Solution {
public int integerBreak(int n) {
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
int result = 0;
for (int i = 2; i <= n; i++) {
int max = -1;
for (int j = 1; j < i; j++) {
max = Math.max(Math.max(dp[j] * (i - j), j * (i - j)), max);
}
dp[i] = max;
if (i == n) {
result = Math.max(result, max);
}
}
return result;
}
}