本文主要是介绍力扣第343题 整数拆分 c++ 动态规划 + 贪心巧解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
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
思路和解题方法(已优化)
- 首先，我们定义一个一维数组
dp，其中dp[i]表示将正整数i拆分成若干个正整数的和后，这些正整数的乘积的最大值。- 接下来，我们进行动态规划的计算。外层循环从3开始，因为对于小于等于2的正整数，无法拆分成多个正整数的和，所以最大乘积就是其本身。内层循环从1遍历到
i / 2，表示在正整数i上进行拆分。- 对于每个内层循环中的位置
(i, j)，我们有两种选择：要么将正整数i拆分成长度为j和(i-j)的两个正整数，要么不再进行拆分。如果选择拆分，那么乘积就是(i - j) * j；如果选择不再拆分，那么乘积就是dp[i - j] * j。我们需要取这两者之间的较大值，然后更新dp[i]。- 最终，当外层循环结束时，
dp[n]就表示将正整数n拆分成若干个正整数的和后，这些正整数的乘积的最大值。
复杂度
时间复杂度:
O(n^2)
- 时间复杂度为O(n^2)，因为有两层循环嵌套。其中，外层循环从3到n，内层循环从1到
i / 2。
空间复杂度
O(n)
空间复杂度为O(n)，因为只使用了一个大小为n+1的一维数组
dp。
c++ 代码
class Solution {
public:int integerBreak(int n) {vector<int> dp(n + 1); // 创建一个大小为n+1的一维数组dp，用于存储拆分整数i后的最大乘积dp[2] = 1; // 对于整数2，无法进行拆分，最大乘积就是其本身for (int i = 3; i <= n ; i++) { // 从3开始遍历到nfor (int j = 1; j <= i / 2; j++) { // 在整数i上进行拆分，内层循环从1遍历到i/2// 选择将整数i拆分成长度为j和(i-j)的两个部分或者不再进行拆分，取两者之间的较大值dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));}}return dp[n]; // 返回将整数n拆分成若干个正整数之和后，这些正整数的乘积的最大值}
};
附贪心思维
解释
- 首先处理一些特殊情况，当n等于2、3、4时，直接返回对应的结果，因为这些情况无法再进行拆分。
- 初始化一个变量
result为1，用于保存最终的乘积结果。- 当n大于4时，不断循环执行以下步骤：
- 将
result乘以3，表示将n拆分出一个长度为3的部分。- 将n减去3，表示已经拆分出了一个长度为3的部分。
- 循环结束后，剩余的n的取值只能是2、3或者4。将
result乘以剩余的n，得到最终的乘积结果。- 返回最终的乘积结果。
class Solution {
public:int integerBreak(int n) {if (n == 2) return 1; // 对于整数2，无法进行拆分，最大乘积就是其本身（1 * 1 = 1）if (n == 3) return 2; // 对于整数3，可以拆分为1 + 2，乘积为1 * 2 = 2if (n == 4) return 4; // 对于整数4，可以拆分为2 + 2，乘积为2 * 2 = 4int result = 1;while (n > 4) {result *= 3; // 每次将n拆分成3的部分，因为3的乘积比其他数字更大n -= 3;}result *= n; // 最后剩下的n小于等于4，直接乘到结果中return result;}
};
觉得有用的话可以点点赞，支持一下。
如果愿意的话关注一下。会对你有更多的帮助。
每天都会不定时更新哦 >人< 。
这篇关于力扣第343题 整数拆分 c++ 动态规划 + 贪心巧解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
