Keshawn_lu's Blog

Leetcode 343. 整数拆分

字数统计: 335阅读时长: 1 min
2020/07/30 Share

题目简介:

给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

示例 1:

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

示例 2:

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

说明: 你可以假设 n 不小于 2 且不大于 58。

思路:

动态规划,dp[i]代表正整数i,拆分为至少两个正整数的和,并使这些整数的乘积最大化,可以获得的最大乘积。

所以对于一个正整数i >= 2,乘积的最大值存在以下两种情况:

  1. i分为j, i - j,并且i - j不再分离,此时乘积为j * (i - j)
  2. i分为j, i - j,并把i - j继续分离,此时乘积为j * dp[i - j]

所以我们只要遍历j,从1 ~ i - 1,在过程中记录最大值,最后赋值给dp[i]即可。

最后返回dp[n]即可。

tip:

  • dp[0] = dp[1] = 0。(不可分离)

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int integerBreak(int n) {

vector<int> dp(n + 1, 0);

for(int i = 2; i <= n; i++){

int temp = 0;
for(int j = 1; j < i; j++){

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

dp[i] = temp;
}

return dp[n];

}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: