343. 整數(shù)拆分

題目鏈接：343. 整數(shù)拆分
參考：https://programmercarl.com/0343.%E6%95%B4%E6%95%B0%E6%8B%86%E5%88%86.html

題目描述

給定一個(gè)正整數(shù) n，將其拆分為至少兩個(gè)正整數(shù)的和，并使這些整數(shù)的乘積最大化。 返回你可以獲得的最大乘積。

示例 1:

• 輸入: 2
• 輸出: 1
• 解釋: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

• 輸入: 10

• 輸出: 36

• 解釋: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

• 說(shuō)明: 你可以假設(shè) n 不小于 2 且不大于 58。

思路

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

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

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

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

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

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

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

2. 確定遞推公式

可以想 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é)問(wèn)了，j怎么就不拆分呢？

j是從1開始遍歷，拆分j的情況，在遍歷j的過(guò)程中其實(shí)都計(jì)算過(guò)了。那么從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)的過(guò)程中，因?yàn)?i固定，j在遍歷，每次計(jì)算dp[i]，取最大的而已。

3. dp的初始化

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

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

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

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

這是無(wú)解的。

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

4. 確定遍歷順序

確定遍歷順序，先來(lái)看看遞歸公式：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 也是可以的，不過(guò)可以節(jié)省一步，例如讓j = i - 1，的話，其實(shí)在 j = 1的時(shí)候，這一步就已經(jīng)拆出來(lái)了，重復(fù)計(jì)算，所以 j < i - 1

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

更優(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)?strong>拆分一個(gè)數(shù)n 使之乘積最大，那么一定是拆分成m個(gè)近似相同的子數(shù)相乘才是最大的。

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

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

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

5. 舉例推導(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)

這里注意取最大值時(shí)要多加一個(gè){}。

貪心

本題也可以用貪心，每次拆成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í)簡(jiǎn)單，但需要有數(shù)學(xué)證明，如果能自圓其說(shuō)也是可以的。

96.不同的二叉搜索樹

題目鏈接：96.不同的二叉搜索樹
參考：https://programmercarl.com/0096.%E4%B8%8D%E5%90%8C%E7%9A%84%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html

題目描述

給定一個(gè)整數(shù) n，求以 1 … n 為節(jié)點(diǎn)組成的二叉搜索樹有多少種？

示例:

思路

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

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

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

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

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

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

（可能有同學(xué)問(wèn)了，這布局不一樣啊，節(jié)點(diǎn)數(shù)值都不一樣。別忘了我們就是求不同樹的數(shù)量，并不用把搜索樹都列出來(lái)，所以不用關(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í)我們就找到了重疊子問(wèn)題了，其實(shí)也就是發(fā)現(xiàn)可以通過(guò)dp[1] 和 dp[2] 來(lái)推導(dǎo)出來(lái)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] ，都是一樣的。

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

2. 確定遞推公式
   在上面的分析中，其實(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ù)量

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

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

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

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

從遞歸公式上來(lái)講，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

4. 確定遍歷順序
   首先一定是遍歷節(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來(lái)遍歷。

代碼如下：

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

5. 舉例推導(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ù)組打出來(lái)，看看哪里有問(wèn)題。

綜上分析完畢，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)$

總結(jié)

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

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

然后難點(diǎn)就是確定遞推公式了，如果把遞推公式想清楚了，遍歷順序和初始化，就是自然而然的事情了。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-423811.html

到了這里，關(guān)于算法訓(xùn)練第四十一天|343. 整數(shù)拆分 、96.不同的二叉搜索樹的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！