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的索引，包含nvector<int> dp(n+1,0);// 动态规划开始，从2遍历到n，因为我们要求解的是2到n的整数拆分for(int i=2;i<=n;i++){// 内循环，考虑将整数i拆分为两个数：j和i-j// 因为拆分成更多的数可以由这两个数继续拆分得到，所以只需要考虑到i/2for(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拆分后的最大乘积。