343. 整数拆分
题目描述
给定一个正整数 n ,将其拆分为 k 个 正整数 的和( k >= 2 ),并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
示例 1:
输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
提示:
- 2 <= n <= 58
动态规划
下面是代码的详细注释:
class Solution {
public:
int integerBreak(int n) {
// 初始化一个大小为n+1的动态数组(向量)dp,以0填充
// n+1是因为我们想要一个从0到n的索引,包含n
vector<int> dp(n+1,0);
// 动态规划开始,从2遍历到n,因为我们要求解的是2到n的整数拆分
for(int i=2;i<=n;i++)
{
// 内循环,考虑将整数i拆分为两个数:j和i-j
// 因为拆分成更多的数可以由这两个数继续拆分得到,所以只需要考虑到i/2
for(int j=1;j<=i/2;j++)
{
// dp[i]表示整数i拆分后的最大乘积
// 我们检查两种情况:
// 1. j * (i - j):直接将i拆分为j和i-j的乘积
// 2. j * dp[i - j]:将i拆分为j和拆分(i-j)后得到的最大乘积
// 使用max函数来比较并取这两种拆分方式的较大者
// 然后再与当前dp[i]的值比较,取较大值更新dp[i]
dp[i]=max(dp[i],max(j*(i-j),j*dp[i-j]));
}
}
// 在完成上面的动态规划循环后,dp[n]存储了整数n拆分后的最大乘积
// 最后返回该最大乘积
return dp[n];
}
};
这段代码实现了一个动态规划算法,用于解决给定的正整数n的整数拆分问题,旨在找出拆分后的整数的乘积最大值。代码首先初始化一个动态规划数组dp
,大小为n+1
以包含从0
到n
的所有整数拆分的结果,初始值为0
。接着,通过双层循环构建出dp
数组的每一个元素。外层循环遍历所有待拆分的整数i
,内层循环遍历可能的拆分位置j
。在内层循环中,通过比较不同拆分方式得到的乘积,来决定最大乘积是直接拆分为j
和i-j
的乘积,还是拆分为j
和拆分i-j
后得到的最大乘积,最后更新dp[i]
为这些可能中的最大值。动态规划完成后,dp[n]
中存储的就是题目要求的整数n拆分后的最大乘积。