LC343题解 | #整数拆分#
动态规划
动归三部曲：
dp[i] 是啥？ dp[i] 表示的是数字 i 所拥有的最大乘积
dp[i] 的递推公式？dp[i] = Math.max(dp[i], Math.max(j*(i-j), j*dp[i-j])); 下面会有解释
dp[i] 的初始化？ 我们只需要初始化dp[2]，从3开始遍历即可，因为dp[1] 和dp[0] 没有意义
为什么递推公式是这样的？
因为dp[i]只要放i的最大乘积即可，因此max取一个dp[i]。
内层max表示的是：两个数的乘积和多个数的乘积取max。
两个数的乘积为当前的因子j和(i-j)，
多个数的没法直接求，因为不好控制具体几个因子，所以交给前一位dp[i-1]。
证明：i = 1 + (i-1)，所以dp[i] = 1 * dp[i-1]
则有：i = j + (i-j)，所以dp[i] = j * dp[i-j]
dp[i] = 1 * dp[i-1]只是一个特例
class Solution {
public int integerBreak(int n) {
int[] dp = new int[n + 1]; // dp[i]表示数字i的最大乘积
// 为什么是n+1，因为长度为n只能求到dp[0]~dp[n-1]，所以要加一位才能求到dp[n]
dp[2] = 1; // 题干给的初始化，从2开始
for (int i = 3; i <= n; ++i) { // 从dp[3]开始遍历，向后填充直到dp[n]
// 分解i的第一个因子，到i-j结束，多了就重复了
for (int j = 1; j <= i-j; ++j) {
dp[i] = Math.max(dp[i], Math.max(j*(i-j), j*dp[i-j]));
}
}
return dp[n];
}
}
查看10道真题和解析