[Vssue]0343.整数拆分.md

int[] dp = new int[n + 1];
dp[2] = 1;
for (int i = 3; i <= n; i++) {
    for (int j = 1; j <= i / 2; j++) {
        dp[i] = Math.max(dp[i], Math.max((i - j) * j, dp[i - j] * j));
    }
}
return dp[n];

// 例: n = 5, dp = [0,0,1,0,0,0]
i = 3:  j = 1: dp[3] = max(0, 2 * 1, 1 * 1) = 2, dp = [0,0,1,2,0,0]
i = 4:  j = 1: dp[4] = max(0, 3 * 1, 2 * 1) = 3
        j = 2: dp[4] = max(3, 2 * 2, 1 * 2) = 4, dp = [0,0,1,2,4,0]
i = 5:  j = 1: dp[5] = max(0, 4 * 1, 4 * 1) = 4
        j = 2: dp[5] = max(4, 3 * 2, 2 * 2) = 6, dp = [0,0,1,2,4,6]

youngyangyang04 / leetcode-master-comment

[Vssue]0343.整数拆分.md #179