343. 整數(shù)拆分

文章目錄

• • [343. 整數(shù)拆分](https://leetcode.cn/problems/integer-break/)
  • • 一、題目
    • 二、題解
    • • 方法一：動態(tài)規(guī)劃
      • 方法改良

---

一、題目

給定一個(gè)正整數(shù) n ，將其拆分為 k 個(gè) 正整數(shù) 的和（ k >= 2 ），并使這些整數(shù)的乘積最大化。

返回 你可以獲得的最大乘積 。

示例 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

二、題解

方法一：動態(tài)規(guī)劃

好的，讓我們按照動態(tài)規(guī)劃的五個(gè)步驟來解決這道題目：

步驟一：確認(rèn)dp數(shù)組以及下標(biāo)的含義

• dp[i] 表示正整數(shù) i 拆分后可以獲得的最大乘積。

步驟二：確認(rèn)遞推公式

• 對于正整數(shù) i，我們可以把它拆分成兩個(gè)正整數(shù) j 和 i-j，其中 1 <= j < i。
• 那么，對于拆分的兩個(gè)正整數(shù) j 和 i-j，可以計(jì)算它們的乘積 max(j * (i-j))。
• 但我們還需要考慮 j 和 i-j 是否繼續(xù)拆分，因此遞推公式為 dp[i] = max(max(j * (i-j), j * dp[i-j]), max(dp[j] * (i-j), dp[j] * dp[i-j]))。

步驟三：數(shù)組初始化

• dp[1] 和 dp[2] 的值分別為 0 和 1，因?yàn)樗鼈兌疾荒茉俨鸱帧?/li>

步驟四：確定遍歷順序

• 我們從小到大遍歷正整數(shù) i，從 3 開始遍歷到 n，依次計(jì)算 dp[i] 的值。

步驟五：舉例推導(dǎo)dp數(shù)組
讓我們通過一個(gè)示例來推導(dǎo) dp 數(shù)組。假設(shè)輸入 n = 6：

進(jìn)行推導(dǎo)：

1. 初始化 dp 數(shù)組：

dp = [0, 1]

2. 計(jì)算 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

3. 計(jì)算 dp[4]：

dp[4] = 4

4. 計(jì)算 dp[5]：

dp[5] = 6

5. 計(jì)算 dp[6]：

dp[6] = 9

最終返回 dp[n]，即 dp[6] = 9，表示將正整數(shù) 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是一個(gè)改善措施，因?yàn)楫?dāng)j>i/2后所有的情況之前都已經(jīng)產(chǎn)生過了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];}
};

方法改良

在遞推公式的計(jì)算部分，我們可以將遞推公式簡化為 dp[i] = max(j * k, j * dp[k])，并且不再計(jì)算 dp[j] * dp[k] 部分。

改良的原因：

• 在原始的遞推公式中，我們考慮了 j 和 k 是否繼續(xù)拆分，計(jì)算了 dp[j] * dp[k] 部分，但實(shí)際上，這部分是在之前的狀態(tài)中已經(jīng)計(jì)算過的，而且不會再參與當(dāng)前狀態(tài)的計(jì)算。
• 因此，我們可以直接在遞推公式中計(jì)算 j * dp[k] 部分，而不再重復(fù)計(jì)算之前已經(jīng)得到的 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];}
};