343. 整數(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。
說明: 你可以假設 n 不小于 2 且不大于 58。

思路分析

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

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

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

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

2. 確定遞推公式

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

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

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

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

那有同學問了，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));

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

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

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

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

因為在遞推公式推導的過程中，每次計算dp[i]，取最大的而已。

3. dp的初始化

不少同學應該疑惑，dp[0] dp[1]應該初始化多少呢？

有的題解里會給出dp[0] = 1，dp[1] = 1的初始化，但解釋比較牽強，主要還是因為這么初始化可以把題目過了。

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

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

這是無解的。

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

4. 確定遍歷順序

確定遍歷順序，先來看看遞歸公式：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]。

所以遍歷順序為：

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的時候，是從1開始的。從0開始的話，那么讓拆分一個數(shù)拆個0，求最大乘積就沒有意義了。

j的結束條件是 j < i - 1 ，其實 j < i 也是可以的，不過可以節(jié)省一步，例如讓j = i - 1，的話，其實在 j = 1的時候，這一步就已經拆出來了，重復計算，所以 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));
    }
}

因為拆分一個數(shù)n 使之乘積最大，那么一定是拆分成m個近似相同的子數(shù)相乘才是最大的。

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

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

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

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

5. 舉例推導dp數(shù)組

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

代碼實現(xiàn)

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

96.不同的二叉搜索樹

題目鏈接????
給定一個整數(shù) n，求以 1 … n 為節(jié)點組成的二叉搜索樹有多少種？

示例:

思路分析

舉幾個例子，畫畫圖，看看有沒有什么規(guī)律，如圖：

n為1的時候有一棵樹，n為2有兩棵樹，這個是很直觀的。

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

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

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

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

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

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

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

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

元素1為頭結點搜索樹的數(shù)量 = 右子樹有2個元素的搜索樹數(shù)量 * 左子樹有0個元素的搜索樹數(shù)量

元素2為頭結點搜索樹的數(shù)量 = 右子樹有1個元素的搜索樹數(shù)量 * 左子樹有1個元素的搜索樹數(shù)量

元素3為頭結點搜索樹的數(shù)量 = 右子樹有0個元素的搜索樹數(shù)量 * 左子樹有2個元素的搜索樹數(shù)量

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

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

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

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

如圖所示：

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

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

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

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

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

2. 確定遞推公式

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

j相當于是頭結點的元素，從1遍歷到i為止。

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

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

初始化，只需要初始化dp[0]就可以了，推導的基礎，都是dp[0]。

那么dp[0]應該是多少呢？

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

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

所以初始化dp[0] = 1

4. 確定遍歷順序

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

那么遍歷i里面每一個數(shù)作為頭結點的狀態(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];
    }
}

5. 舉例推導dp數(shù)組

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

當然如果自己畫圖舉例的話，基本舉例到n為3就可以了，n為4的時候，畫圖已經比較麻煩了。

我這里列到了n為5的情況，是為了方便大家 debug代碼的時候，把dp數(shù)組打出來，看看哪里有問題。文章來源地址http://www.zghlxwxcb.cn/news/detail-695440.html

代碼實現(xiàn)

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

到了這里，關于算法訓練day41|動態(tài)規(guī)劃 part03(LeetCode343. 整數(shù)拆分、96.不同的二叉搜索樹)的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！