力扣AC：整数拆分 - 动态规划

题目链接

整数拆分

题目描述

实现代码

动态规划思想：记dp[i]表示数字i的拆分次数，我们最终要求的是dp[n]，首先初始化条件：

1. dp[0] = 0
2. 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;
    }
}