解题思路

按照动规五部曲

  1. 确定dp数组及其下标的含义

    dp[i], i为要被拆分的整数，dp[i]为要被拆分的整数的最大乘积

  2. 确定递推公式

    dp[i] = max(dp[i], j * (i - j), j * dp[i - j])

    j * (i - j)是将数字拆分成两个正整数时的最大值

    j * dp[i - j] 是将数字拆分成两个以上时的最大值，由于dp[i]前面以及被计算过了，所以可以直接得出拆分更多正整数的乘积

  3. 初始化dp数组

    整数拆分0和1没有任何意义，所以只要关注2就行了,dp[2] = 1

  4. 确定遍历顺序

    i从3开始遍历

    j从1开始遍历

  5. 举例推导dp数组

代码

Python

1
2
3
4
5
6
7
8
class Solution:
    def integerBreak(self, n: int) -> int:
        dp = [0 for _ in range(n + 1)]
        dp[2] = 1
        for i in range(3, n + 1):
            for j in range(1, i - 1):
                dp[i] = max(dp[i], (i - j) * j, dp[i - j] * j)
        return dp[n]

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n + 1);
        dp[2] = 1;
        for (int i = 3; i < n + 1; i++) {
            for (int j = 1; j < i - 1; j++) {
                dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }
};

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func integerBreak(n int) int {
    dp := make([]int, n + 1)
    dp[2] = 1
    for i := 3; i < n + 1; i++ {
        for j := 1; j < i - 1; j++ {
            dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))
        }
    }
    return dp[n]
}

func max(a int, b int) int {
    if a >= b {return a}
    return b
}