建站
咨詢
售后
建站咨詢
新聞中心
整數(shù)拆分
10年積累的網(wǎng)站設(shè)計制作、成都做網(wǎng)站經(jīng)驗，可以快速應(yīng)對客戶對網(wǎng)站的新想法和需求。提供各種問題對應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認(rèn)識你，你也不認(rèn)識我。但先網(wǎng)站設(shè)計后付款的網(wǎng)站建設(shè)流程，更有蘭坪免費網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。
給定一個正整數(shù) n，將其拆分為至少兩個正整數(shù)的和，并使這些整數(shù)的乘積最大化。返回你可以獲得的最大乘積。
示例1:
- 輸入: 2
- 輸出: 1
- 解釋: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
- 輸入: 10
- 輸出: 36
- 解釋: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
- 說明: 你可以假設(shè) n 不小于 2 且不大于 58。
思路
看到這道題目，都會想拆成兩個呢，還是三個呢，還是四個....
我們來看一下如何使用動規(guī)來解決。
動態(tài)規(guī)劃
動規(guī)五部曲，分析如下：
1.確定dp數(shù)組(dp table)以及下標(biāo)的含義
dp[i]：分拆數(shù)字i，可以得到的最大乘積為dp[i]。
dp[i]的定義講貫徹整個解題過程，下面哪一步想不懂了，就想想dp[i]究竟表示的是啥!
2.確定遞推公式
可以想 dp[i]最大乘積是怎么得到的呢?
其實可以從1遍歷j，然后有兩種渠道得到dp[i].
一個是j * (i - j) 直接相乘。
一個是j * dp[i - j]，相當(dāng)于是拆分(i - j)，對這個拆分不理解的話，可以回想dp數(shù)組的定義。
那有同學(xué)問了，j怎么就不拆分呢?
j是從1開始遍歷，拆分j的情況，在遍歷j的過程中其實都計算過了。
那么從1遍歷j，比較(i - j) * j和dp[i - j] * j 取最大的。
遞推公式：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
3.dp的初始化
不少同學(xué)應(yīng)該疑惑，dp[0] dp[1]應(yīng)該初始化多少呢?
有的題解里會給出dp[0] = 1，dp[1] = 1的初始化，但解釋比較牽強，主要還是因為這么初始化可以把題目過了。
嚴(yán)格從dp[i]的定義來說，dp[0] dp[1] 就不應(yīng)該初始化，也就是沒有意義的數(shù)值。
拆分0和拆分1的最大乘積是多少?
這是無解的。
這里我只初始化dp[2] = 1，從dp[i]的定義來說，拆分?jǐn)?shù)字2，得到的最大乘積是1，這個沒有任何異議!
確定遍歷順序
確定遍歷順序，先來看看遞歸公式：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
dp[i] 是依靠 dp[i - j]的狀態(tài)，所以遍歷i一定是從前向后遍歷，先有dp[i - j]再有dp[i]。
枚舉j的時候，是從1開始的。i是從3開始，這樣dp[i - j]就是dp[2]正好可以通過我們初始化的數(shù)值求出來。
所以遍歷順序為：
- for (int i = 3; i <= n ; i++) {
- for (int j = 1; j < i - 1; j++) {
- dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
- }
- }
舉例推導(dǎo)dp數(shù)組
舉例當(dāng)n為10 的時候，dp數(shù)組里的數(shù)值，如下：
343.整數(shù)拆分
以上動規(guī)五部曲分析完畢，C++代碼如下：
- class Solution {
- public:
- int integerBreak(int n) {
- vector
dp(n + 1); - dp[2] = 1;
- for (int i = 3; i <= n ; i++) {
- for (int j = 1; j < i - 1; j++) {
- dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
- }
- }
- return dp[n];
- }
- };
- 時間復(fù)雜度：O(n^2)
- 空間復(fù)雜度：O(n)
貪心
本題也可以用貪心，每次拆成n個3，如果剩下是4，則保留4，然后相乘，但是這個結(jié)論需要數(shù)學(xué)證明其合理性!
我沒有證明，而是直接用了結(jié)論。感興趣的同學(xué)可以自己再去研究研究數(shù)學(xué)證明哈。
給出我的C++代碼如下：
- class Solution {
- public:
- int integerBreak(int n) {
- if (n == 2) return 1;
- if (n == 3) return 2;
- if (n == 4) return 4;
- int result = 1;
- while (n > 4) {
- result *= 3;
- n -= 3;
- }
- result *= n;
- return result;
- }
- };
- 時間復(fù)雜度O(n)
- 空間復(fù)雜度O(1)
總結(jié)
本題掌握其動規(guī)的方法，就可以了，貪心的解法確實簡單，但需要有數(shù)學(xué)證明，如果能自圓其說也是可以的。
其實這道題目的遞推公式并不好想，而且初始化的地方也很有講究，我在寫本題的時候一開始寫的代碼是這樣的：
- class Solution {
- public:
- int integerBreak(int n) {
- if (n <= 3) return 1 * (n - 1);
- vector
dp(n + 1, 0); - dp[1] = 1;
- dp[2] = 2;
- dp[3] = 3;
- for (int i = 4; i <= n ; i++) {
- for (int j = 1; j < i - 1; j++) {
- dp[i] = max(dp[i], dp[i - j] * dp[j]);
- }
- }
- return dp[n];
- }
- };
這個代碼也是可以過的!
在解釋遞推公式的時候，也可以解釋通，dp[i] 就等于 拆解i - j的最大乘積 * 拆解j的最大乘積?？雌饋頉]毛病!
但是在解釋初始化的時候，就發(fā)現(xiàn)自相矛盾了，dp[1]為什么一定是1呢?根據(jù)dp[i]的定義，dp[2]也不應(yīng)該是2啊。
但如果遞歸公式是 dp[i] = max(dp[i], dp[i - j] * dp[j]);，就一定要這么初始化。遞推公式?jīng)]毛病，但初始化解釋不通!
雖然代碼在初始位置有一個判斷if (n <= 3) return 1 * (n - 1);，保證n<=3 結(jié)果是正確的，但代碼后面又要給dp[1]賦值1 和 dp[2] 賦值 2，這其實就是自相矛盾的代碼，違背了dp[i]的定義!
我舉這個例子，其實就說做題的嚴(yán)謹(jǐn)性，上面這個代碼也可以AC，大體上一看好像也沒有毛病，遞推公式也說得過去，但是僅僅是恰巧過了而已。
本文轉(zhuǎn)載自微信公眾號「代碼隨想錄」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系代碼隨想錄公眾號。
新聞名稱：動態(tài)規(guī)劃：整數(shù)拆分，你要怎么拆？
文章位置：http://www.dlmjj.cn/article/cdoipds.html
