343. 整数拆分
文章目录
- [343. 整数拆分](https://leetcode.cn/problems/integer-break/)
- 一、题目
- 二、题解
- 方法一：动态规划
- 方法改良
一、题目
给定一个正整数 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 拆分后可以获得的最大乘积。
步骤二：确认递推公式
- 对于正整数 i，我们可以把它拆分成两个正整数 j 和 i-j，其中 1 <= j < i。
- 那么，对于拆分的两个正整数 j 和 i-j，可以计算它们的乘积 max(j * (i-j))。
- 但我们还需要考虑 j 和 i-j 是否继续拆分，因此递推公式为 dp[i] = max(max(j * (i-j), j * dp[i-j]), max(dp[j] * (i-j), dp[j] * dp[i-j]))。
步骤三：数组初始化
- dp[1] 和 dp[2] 的值分别为 0 和 1，因为它们都不能再拆分。
步骤四：确定遍历顺序
- 我们从小到大遍历正整数 i，从 3 开始遍历到 n，依次计算 dp[i] 的值。
步骤五：举例推导dp数组
让我们通过一个示例来推导 dp 数组。假设输入 n = 6：
进行推导：
- 初始化 dp 数组：
dp = [0, 1]
- 计算 dp[3]：
dp[3] = max(max(1*(3-1), 1*dp[3-1]), max(dp[1]*(3-1), dp[1]*dp[3-1])) = max(max(1*2, 1*1), max(0*2, 0*1)) = 2
- 计算 dp[4]：
dp[4] = 4
- 计算 dp[5]：
dp[5] = 6
- 计算 dp[6]：
dp[6] = 9
最终返回 dp[n]，即 dp[6] = 9，表示将正整数 6 拆分后可以获得的最大乘积为 9。
class Solution {
public:int integerBreak(int n) {vector<int> dp(n+1);dp[1] = 0;dp[2] = 1;for(int i = 3; i <= n; i++){int maxm = 1;//i/2是一个改善措施，因为当j>i/2后所有的情况之前都已经产生过了for(int j = 1; j <= i/2; j++){int k = i-j;int temp = max(max(j*k,dp[j]*k),max(dp[k]*j,dp[j]*dp[k]));if(maxm < temp) maxm = temp;}dp[i] = maxm;}return dp[n];}
};
方法改良
在递推公式的计算部分，我们可以将递推公式简化为 dp[i] = max(j * k, j * dp[k])，并且不再计算 dp[j] * dp[k] 部分。
改良的原因：
- 在原始的递推公式中，我们考虑了 j 和 k 是否继续拆分，计算了 dp[j] * dp[k] 部分，但实际上，这部分是在之前的状态中已经计算过的，而且不会再参与当前状态的计算。
- 因此，我们可以直接在递推公式中计算 j * dp[k] 部分，而不再重复计算之前已经得到的 dp[j]。
改良后的代码如下：
cppCopy codeclass Solution {
public:int integerBreak(int n) {vector<int> dp(n + 1);dp[2] = 1;for (int i = 3; i <= n; i++) {int maxm = 1;for (int j = 1; j <= i / 2; j++) {int k = i - j;int temp = max(j * k, j * dp[k]);if (maxm < temp) maxm = temp;}dp[i] = maxm;}return dp[n];}
};
