跳转至

343. 整数拆分

力扣链接(中等)：https://leetcode.cn/problems/integer-break

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

示例 1:

Text Only
1
2
3
输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

Text Only
1
2
3
输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

提示:

  • 2 <= n <= 58

个人题解

  1. 确定 dp 数组：dp[i] 代表拆分正整数 i 获得的最大乘积；
  2. 确定递推公式：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j))，可以这样理解， (i - j) * j 是把整数 i 拆分为 i - j 和 j 相乘，dp[i - j] * j 相当于把整数 i 拆分为 j 和 dp[i - j]，而 dp[i - j] 代表整数 i - j 的若干拆分情况中乘积最大的一种；
  3. dp 数组初始化，根据 dp 数组定义，dp[0-1] 没有初始化的意义，因为无法拆分，只需要从 2 开始拆分即可，即 dp[2] = 1；
  4. 确定遍历顺序：由递推公式，遍历顺序应该为从大到小；
  5. 举例推导 dp 数组，合理。
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int integerBreak(int n) {
        const int N = 60;
        int dp[N] = {};

        dp[2] = 1;

        for(int i = 3; i <= n; i++) {
            for(int j = 1; j < i; j++) {
                dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
            }
        }

        return dp[n];
    }
};