本文章代碼以c++為例！

一、力扣第343題：整數(shù)拆分

題目：

給定一個(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

思路

看到這道題目，都會(huì)想拆成兩個(gè)呢，還是三個(gè)呢，還是四個(gè)....

我們來看一下如何使用動(dòng)規(guī)來解決。

# 動(dòng)態(tài)規(guī)劃

動(dòng)規(guī)五部曲，分析如下：

1. 確定dp數(shù)組（dp table）以及下標(biāo)的含義

dp[i]：分拆數(shù)字i，可以得到的最大乘積為dp[i]。

dp[i]的定義將貫徹整個(gè)解題過程，下面哪一步想不懂了，就想想dp[i]究竟表示的是啥！

1. 確定遞推公式

可以想 dp[i]最大乘積是怎么得到的呢？

其實(shí)可以從1遍歷j，然后有兩種渠道得到dp[i].

一個(gè)是j * (i - j) 直接相乘。

一個(gè)是j * dp[i - j]，相當(dāng)于是拆分(i - j)，對(duì)這個(gè)拆分不理解的話，可以回想dp數(shù)組的定義。

那有同學(xué)問了，j怎么就不拆分呢？

j是從1開始遍歷，拆分j的情況，在遍歷j的過程中其實(shí)都計(jì)算過了。那么從1遍歷j，比較(i - j) * j和dp[i - j] * j 取最大的。遞推公式：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));

也可以這么理解，j * (i - j) 是單純的把整數(shù)拆分為兩個(gè)數(shù)相乘，而j * dp[i - j]是拆分成兩個(gè)以及兩個(gè)以上的個(gè)數(shù)相乘。

如果定義dp[i - j] * dp[j] 也是默認(rèn)將一個(gè)數(shù)強(qiáng)制拆成4份以及4份以上了。

所以遞推公式：dp[i] = max({dp[i], (i - j) * j, dp[i - j] * j});

那么在取最大值的時(shí)候，為什么還要比較dp[i]呢？

因?yàn)樵谶f推公式推導(dǎo)的過程中，每次計(jì)算dp[i]，取最大的而已。

1. dp的初始化

不少同學(xué)應(yīng)該疑惑，dp[0] dp[1]應(yīng)該初始化多少呢？

有的題解里會(huì)給出dp[0] = 1，dp[1] = 1的初始化，但解釋比較牽強(qiáng)，主要還是因?yàn)檫@么初始化可以把題目過了。

嚴(yán)格從dp[i]的定義來說，dp[0] dp[1] 就不應(yīng)該初始化，也就是沒有意義的數(shù)值。

拆分0和拆分1的最大乘積是多少？

這是無解的。

這里我只初始化dp[2] = 1，從dp[i]的定義來說，拆分?jǐn)?shù)字2，得到的最大乘積是1，這個(gè)沒有任何異議！

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]。

所以遍歷順序?yàn)椋?/p>

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));
    }
}

注意 枚舉j的時(shí)候，是從1開始的。從0開始的話，那么讓拆分一個(gè)數(shù)拆個(gè)0，求最大乘積就沒有意義了。

j的結(jié)束條件是 j < i - 1 ，其實(shí) j < i 也是可以的，不過可以節(jié)省一步，例如讓j = i - 1，的話，其實(shí)在 j = 1的時(shí)候，這一步就已經(jīng)拆出來了，重復(fù)計(jì)算，所以 j < i - 1

至于 i是從3開始，這樣dp[i - j]就是dp[2]正好可以通過我們初始化的數(shù)值求出來。

更優(yōu)化一步，可以這樣：

for (int i = 3; i <= n ; i++) {
    for (int j = 1; j <= i / 2; j++) {
        dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
    }
}

因?yàn)椴鸱忠粋€(gè)數(shù)n 使之乘積最大，那么一定是拆分成m個(gè)近似相同的子數(shù)相乘才是最大的。

例如 6 拆成 3 * 3， 10 拆成 3 * 3 * 4。 100的話 也是拆成m個(gè)近似數(shù)組的子數(shù) 相乘才是最大的。

只不過我們不知道m(xù)究竟是多少而已，但可以明確的是m一定大于等于2，既然m大于等于2，也就是 最差也應(yīng)該是拆成兩個(gè)相同的 可能是最大值。

那么 j 遍歷，只需要遍歷到 n/2 就可以，后面就沒有必要遍歷了，一定不是最大值。

至于 “拆分一個(gè)數(shù)n 使之乘積最大，那么一定是拆分成m個(gè)近似相同的子數(shù)相乘才是最大的” 這個(gè)我就不去做數(shù)學(xué)證明了，感興趣的同學(xué)，可以自己證明。

1. 舉例推導(dǎo)dp數(shù)組

舉例當(dāng)n為10 的時(shí)候，dp數(shù)組里的數(shù)值，如下：

以上動(dòng)規(guī)五部曲分析完畢，C++代碼如下：

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n + 1);
        dp[2] = 1;
        for (int i = 3; i <= n ; i++) {
            for (int j = 1; j <= i / 2; j++) {
                dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
            }
        }
        return dp[n];
    }
};

• 時(shí)間復(fù)雜度：O(n^2)
• 空間復(fù)雜度：O(n)

# 貪心

本題也可以用貪心，每次拆成n個(gè)3，如果剩下是4，則保留4，然后相乘，但是這個(gè)結(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;
    }
};

• 時(shí)間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(1)

# 總結(jié)

本題掌握其動(dòng)規(guī)的方法，就可以了，貪心的解法確實(shí)簡單，但需要有數(shù)學(xué)證明，如果能自圓其說也是可以的。

其實(shí)這道題目的遞推公式并不好想，而且初始化的地方也很有講究，我在寫本題的時(shí)候一開始寫的代碼是這樣的：

class Solution {
public:
    int integerBreak(int n) {
        if (n <= 3) return 1 * (n - 1);
        vector<int> 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 / 2; j++) {
                dp[i] = max(dp[i], dp[i - j] * dp[j]);
            }
        }
        return dp[n];
    }
};

這個(gè)代碼也是可以過的！

在解釋遞推公式的時(shí)候，也可以解釋通，dp[i] 就等于 拆解i - j的最大乘積 * 拆解j的最大乘積。 看起來沒毛?。?/p>

但是在解釋初始化的時(shí)候，就發(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)]毛病，但初始化解釋不通！

雖然代碼在初始位置有一個(gè)判斷if (n <= 3) return 1 * (n - 1);，保證n<=3 結(jié)果是正確的，但代碼后面又要給dp[1]賦值1 和 dp[2] 賦值 2，這其實(shí)就是自相矛盾的代碼，違背了dp[i]的定義！

我舉這個(gè)例子，其實(shí)就說做題的嚴(yán)謹(jǐn)性，上面這個(gè)代碼也可以AC，大體上一看好像也沒有毛病，遞推公式也說得過去，但是僅僅是恰巧過了而已。

二、力扣第98題：不同的二叉搜索樹

題目：

給你一個(gè)整數(shù) n ，求恰由 n 個(gè)節(jié)點(diǎn)組成且節(jié)點(diǎn)值從 1 到 n 互不相同的 二叉搜索樹 有多少種？返回滿足題意的二叉搜索樹的種數(shù)。

示例 1：

輸入：n = 3
輸出：5

示例 2：

輸入：n = 1
輸出：1

提示：

• 1 <= n <= 19

思路

這道題目描述很簡短，但估計(jì)大部分同學(xué)看完都是懵懵的狀態(tài)，這得怎么統(tǒng)計(jì)呢？

關(guān)于什么是二叉搜索樹，我們之前在講解二叉樹專題的時(shí)候已經(jīng)詳細(xì)講解過了，也可以看看這篇二叉樹：二叉搜索樹登場！

(opens new window)再回顧一波。

了解了二叉搜索樹之后，我們應(yīng)該先舉幾個(gè)例子，畫畫圖，看看有沒有什么規(guī)律，如圖：

n為1的時(shí)候有一棵樹，n為2有兩棵樹，這個(gè)是很直觀的。

來看看n為3的時(shí)候，有哪幾種情況。

當(dāng)1為頭結(jié)點(diǎn)的時(shí)候，其右子樹有兩個(gè)節(jié)點(diǎn)，看這兩個(gè)節(jié)點(diǎn)的布局，是不是和 n 為2的時(shí)候兩棵樹的布局是一樣的??！

（可能有同學(xué)問了，這布局不一樣啊，節(jié)點(diǎn)數(shù)值都不一樣。別忘了我們就是求不同樹的數(shù)量，并不用把搜索樹都列出來，所以不用關(guān)心其具體數(shù)值的差異）

當(dāng)3為頭結(jié)點(diǎn)的時(shí)候，其左子樹有兩個(gè)節(jié)點(diǎn)，看這兩個(gè)節(jié)點(diǎn)的布局，是不是和n為2的時(shí)候兩棵樹的布局也是一樣的?。?/p>

當(dāng)2為頭結(jié)點(diǎn)的時(shí)候，其左右子樹都只有一個(gè)節(jié)點(diǎn)，布局是不是和n為1的時(shí)候只有一棵樹的布局也是一樣的??！

發(fā)現(xiàn)到這里，其實(shí)我們就找到了重疊子問題了，其實(shí)也就是發(fā)現(xiàn)可以通過dp[1] 和 dp[2] 來推導(dǎo)出來dp[3]的某種方式。

思考到這里，這道題目就有眉目了。

dp[3]，就是 元素1為頭結(jié)點(diǎn)搜索樹的數(shù)量 + 元素2為頭結(jié)點(diǎn)搜索樹的數(shù)量 + 元素3為頭結(jié)點(diǎn)搜索樹的數(shù)量

元素1為頭結(jié)點(diǎn)搜索樹的數(shù)量 = 右子樹有2個(gè)元素的搜索樹數(shù)量 * 左子樹有0個(gè)元素的搜索樹數(shù)量

元素2為頭結(jié)點(diǎn)搜索樹的數(shù)量 = 右子樹有1個(gè)元素的搜索樹數(shù)量 * 左子樹有1個(gè)元素的搜索樹數(shù)量

元素3為頭結(jié)點(diǎn)搜索樹的數(shù)量 = 右子樹有0個(gè)元素的搜索樹數(shù)量 * 左子樹有2個(gè)元素的搜索樹數(shù)量

有2個(gè)元素的搜索樹數(shù)量就是dp[2]。

有1個(gè)元素的搜索樹數(shù)量就是dp[1]。

有0個(gè)元素的搜索樹數(shù)量就是dp[0]。

所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]

如圖所示：

此時(shí)我們已經(jīng)找到遞推關(guān)系了，那么可以用動(dòng)規(guī)五部曲再系統(tǒng)分析一遍。

1. 確定dp數(shù)組（dp table）以及下標(biāo)的含義

dp[i] ： 1到i為節(jié)點(diǎn)組成的二叉搜索樹的個(gè)數(shù)為dp[i]。

也可以理解是i個(gè)不同元素節(jié)點(diǎn)組成的二叉搜索樹的個(gè)數(shù)為dp[i] ，都是一樣的。

以下分析如果想不清楚，就來回想一下dp[i]的定義

1. 確定遞推公式

在上面的分析中，其實(shí)已經(jīng)看出其遞推關(guān)系， dp[i] += dp[以j為頭結(jié)點(diǎn)左子樹節(jié)點(diǎn)數(shù)量] * dp[以j為頭結(jié)點(diǎn)右子樹節(jié)點(diǎn)數(shù)量]

j相當(dāng)于是頭結(jié)點(diǎn)的元素，從1遍歷到i為止。

所以遞推公式：dp[i] += dp[j - 1] * dp[i - j]; ，j-1 為j為頭結(jié)點(diǎn)左子樹節(jié)點(diǎn)數(shù)量，i-j 為以j為頭結(jié)點(diǎn)右子樹節(jié)點(diǎn)數(shù)量

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

初始化，只需要初始化dp[0]就可以了，推導(dǎo)的基礎(chǔ)，都是dp[0]。

那么dp[0]應(yīng)該是多少呢？

從定義上來講，空節(jié)點(diǎn)也是一棵二叉樹，也是一棵二叉搜索樹，這是可以說得通的。

從遞歸公式上來講，dp[以j為頭結(jié)點(diǎn)左子樹節(jié)點(diǎn)數(shù)量] * dp[以j為頭結(jié)點(diǎn)右子樹節(jié)點(diǎn)數(shù)量] 中以j為頭結(jié)點(diǎn)左子樹節(jié)點(diǎn)數(shù)量為0，也需要dp[以j為頭結(jié)點(diǎn)左子樹節(jié)點(diǎn)數(shù)量] = 1， 否則乘法的結(jié)果就都變成0了。

所以初始化dp[0] = 1

1. 確定遍歷順序

首先一定是遍歷節(jié)點(diǎn)數(shù)，從遞歸公式：dp[i] += dp[j - 1] * dp[i - j]可以看出，節(jié)點(diǎn)數(shù)為i的狀態(tài)是依靠 i之前節(jié)點(diǎn)數(shù)的狀態(tài)。

那么遍歷i里面每一個(gè)數(shù)作為頭結(jié)點(diǎn)的狀態(tài)，用j來遍歷。

代碼如下：

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
        dp[i] += dp[j - 1] * dp[i - j];
    }
}

1. 舉例推導(dǎo)dp數(shù)組

n為5時(shí)候的dp數(shù)組狀態(tài)如圖：

當(dāng)然如果自己畫圖舉例的話，基本舉例到n為3就可以了，n為4的時(shí)候，畫圖已經(jīng)比較麻煩了。

我這里列到了n為5的情況，是為了方便大家 debug代碼的時(shí)候，把dp數(shù)組打出來，看看哪里有問題。

綜上分析完畢，C++代碼如下：

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n + 1);
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
};

• 時(shí)間復(fù)雜度：$O(n^2)$
• 空間復(fù)雜度：$O(n)$

大家應(yīng)該發(fā)現(xiàn)了，我們分析了這么多，最后代碼卻如此簡單！

# 總結(jié)

這道題目雖然在力扣上標(biāo)記是中等難度，但可以算是困難了！

首先這道題想到用動(dòng)規(guī)的方法來解決，就不太好想，需要舉例，畫圖，分析，才能找到遞推的關(guān)系。

然后難點(diǎn)就是確定遞推公式了，如果把遞推公式想清楚了，遍歷順序和初始化，就是自然而然的事情了。

可以看出我依然還是用動(dòng)規(guī)五部曲來進(jìn)行分析，會(huì)把題目的方方面面都覆蓋到！

而且具體這五部分析是我自己平時(shí)總結(jié)的經(jīng)驗(yàn)，找不出來第二個(gè)的，可能過一陣子 其他題解也會(huì)有動(dòng)規(guī)五部曲了，哈哈。

當(dāng)時(shí)我在用動(dòng)規(guī)五部曲講解斐波那契的時(shí)候，一些錄友和我反應(yīng)，感覺講復(fù)雜了。

其實(shí)當(dāng)時(shí)我一直強(qiáng)調(diào)簡單題是用來練習(xí)方法論的，并不能因?yàn)楹唵挝揖痛a一甩，簡單解釋一下就完事了。

可能當(dāng)時(shí)一些同學(xué)不理解，現(xiàn)在大家應(yīng)該感受方法論的重要性了，加油??文章來源地址http://www.zghlxwxcb.cn/news/detail-689475.html

day41補(bǔ)

到了這里，關(guān)于【LeetCode題目詳解】第九章 動(dòng)態(tài)規(guī)劃part03 343. 整數(shù)拆分 96.不同的二叉搜索樹 （day41補(bǔ)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！