很多人覺(jué)得動(dòng)態(tài)規(guī)劃很難，但它就是固定套路而已。其實(shí)動(dòng)態(tài)規(guī)劃只不過(guò)是將多余的步驟，提前放到dp數(shù)組中（就是一個(gè)數(shù)組，只不過(guò)大家都叫它dp），達(dá)到空間換時(shí)間的效果。它僅僅只是一種優(yōu)化思路，因此它目前的境地和線性代數(shù)一樣----虛假的難。

1. 想想線性代數(shù)，在國(guó)外留學(xué)的學(xué)生大多數(shù)不覺(jué)得線性代數(shù)難理解。但是中國(guó)的學(xué)生學(xué)習(xí)線性代數(shù)時(shí)，完全摸不著頭腦，一上來(lái)就是行列式和矩陣，根本不知道這玩意是干嘛的。
2. 線性代數(shù)從根本上是在空間上研究向量，抽象上研究線性關(guān)系的學(xué)科。人家國(guó)外的教科書都是第一講就幫助大家理解研究向量和線性關(guān)系。
3. 反觀國(guó)內(nèi)的教材，直接把行列式搞到第一章。搞的國(guó)內(nèi)的學(xué)生在學(xué)習(xí)線性代數(shù)的時(shí)候，只會(huì)覺(jué)得一知半解，覺(jué)得麻煩，完全不知道這玩意學(xué)來(lái)干什么。當(dāng)苦盡甘來(lái)終于理解線性代數(shù)時(shí)干什么的時(shí)候，發(fā)現(xiàn)人家國(guó)外的教材第一節(jié)就把這玩意講清楚了。你只會(huì)大罵我們國(guó)內(nèi)這些教材，什么狗東西（以上是自己學(xué)完線性代數(shù)后的吐槽，我們同學(xué)無(wú)一例外都這么覺(jué)得）。

而我想告訴你，動(dòng)態(tài)規(guī)劃和線性代數(shù)一樣，我學(xué)完了才知道，它不過(guò)就是研究空間換時(shí)間，提前將固定的重復(fù)操作規(guī)劃到dp數(shù)組中，而不用暴力求解，從而讓效率極大提升。

1. 但是網(wǎng)上教動(dòng)態(tài)規(guī)劃的兄弟們，你直接給一個(gè)動(dòng)態(tài)方程是怎么回事？和線性代數(shù)，一上來(lái)就教行列式和矩陣一樣，純屬惡心人。我差不多做了30多道動(dòng)態(tài)規(guī)劃題目，才理解，動(dòng)態(tài)方程只是一個(gè)步驟而已，而這已經(jīng)浪費(fèi)我很長(zhǎng)時(shí)間了，我每道題都一知半解不理解，過(guò)程及其痛苦。最后只能重新做。
2. 動(dòng)態(tài)規(guī)劃，一定是優(yōu)先考慮重復(fù)操作與dp數(shù)組之間的關(guān)系，搞清楚后，再提出動(dòng)態(tài)方程。而你們前面步驟省略了不講，一上來(lái)給個(gè)方程，不是純屬扯淡嗎？
3. 我推薦研究動(dòng)態(tài)規(guī)劃題目，按5個(gè)步驟，從上到下依次來(lái)分析

1. DP數(shù)組及下標(biāo)含義
2. 遞推公式
3. dp數(shù)組初始化
4. 數(shù)組遍歷順序（雙重循環(huán)及以上時(shí)，才考慮）
5. dp數(shù)組打印，分析思路是否正確（相當(dāng)于做完題，檢查一下）

1. 二叉搜索樹，左子樹都比根結(jié)點(diǎn)小，右子樹都比根結(jié)點(diǎn)大，左右子樹又各是一個(gè)二叉搜索樹。而如果給我們一個(gè)數(shù)3.那么也就是讓我們用①、②、③這3個(gè)結(jié)點(diǎn)構(gòu)成二叉搜索樹。

1. 如果我們用①作根結(jié)點(diǎn)，那么②和③都大于①，只能在它右邊，用②作根結(jié)點(diǎn)，那么①小于②只能放在左邊，③大于②只能放在右邊。
2. 那么左右分多少個(gè)結(jié)點(diǎn)呢？我們發(fā)現(xiàn)，當(dāng)我們截?、谧鳛楦?，①、②、③這個(gè)序列，它左邊的都小于它所有最終都會(huì)在它左邊，同理右邊的都在它右邊。
3. 令j = ②表示以②為根，共有i = 3個(gè)結(jié)點(diǎn)，那么②左邊的，也就是j-1個(gè) = 2-1 = 1個(gè)元素會(huì)被放在左子樹。②右邊的，也就是i - j= 3-2 = 1個(gè)元素會(huì)被放在右邊

2. dp數(shù)組存儲(chǔ)：給你i個(gè)結(jié)點(diǎn)，有幾種擺放方式可以構(gòu)成二叉搜索樹。下標(biāo)i表示當(dāng)前給我們多少結(jié)點(diǎn)可以用于構(gòu)成二叉搜索樹。
3. i = 0時(shí)，只有一種方法組成二叉搜索樹，就是什么都不擺，故，dp[0] = 1
4. i = 1時(shí)，只有一個(gè)結(jié)點(diǎn)①組成二叉搜索樹，只有一個(gè)結(jié)點(diǎn)，只有一種擺放方式，故，dp[1] = 1.
5. i = 2時(shí)，有兩個(gè)結(jié)點(diǎn)①和②可以組成二叉搜索樹，所以我們有兩種思路

1. ①作為根結(jié)點(diǎn)，記為j，左邊有j-1個(gè)元素比它小，右邊有i - j個(gè)元素比它大
2. ②作為根結(jié)點(diǎn)同理。
   
3. 而它的左右子樹，有幾個(gè)元素呢，你會(huì)發(fā)現(xiàn)一定比當(dāng)前的i值小。都不大于2. 那么它們各有幾種擺放方式呢？前面的dp數(shù)組構(gòu)造時(shí)，已經(jīng)考慮過(guò)了i = 0時(shí)，dp[0]=1, i=1時(shí)，dp[1]=1.兩個(gè)相乘，就是以j為根的i個(gè)元素可以構(gòu)造的二叉搜索樹數(shù)量。最后將所有不同根結(jié)點(diǎn)情況相加即可。

1. 暴力求解的思想，就是利用回溯算法，不撞南墻不回頭。
2. 但是如果我們預(yù)先將其存儲(chǔ)到dp數(shù)組，就可以直接通過(guò)dp, 獲取數(shù)據(jù)，而不用枚舉。典型的動(dòng)態(tài)規(guī)劃題目

1. DP數(shù)組及下標(biāo)含義

1. 我們要求出的是給你i個(gè)結(jié)點(diǎn)，可以構(gòu)造出多少種不同二叉搜索樹。顯然dp數(shù)組中存儲(chǔ)的就是i個(gè)結(jié)點(diǎn)，可以構(gòu)造出多少種不同二叉搜索樹。要求出誰(shuí)的？顯然是求出，i個(gè)結(jié)點(diǎn)可構(gòu)造二叉搜索樹數(shù)量。那么下標(biāo)就是代表用幾個(gè)結(jié)點(diǎn)構(gòu)造二叉搜索樹，很顯然，只需要一個(gè)下標(biāo)，也就是一維數(shù)組。

2. 遞推公式

1. 因?yàn)?個(gè)結(jié)點(diǎn)只有一種擺放方式，1個(gè)結(jié)點(diǎn)也只有一種擺放方式，所以：F(0) = F(1) = 1;
2. 對(duì)于其它數(shù)i，我們可以通過(guò)指定不同根結(jié)點(diǎn)，構(gòu)造多種不同二叉搜索樹。我們用j來(lái)表示當(dāng)前用哪個(gè)結(jié)點(diǎn)代表根結(jié)點(diǎn)。例如i = 3，有1,2,3這3個(gè)數(shù)可以構(gòu)造，當(dāng)我們選其中一個(gè)數(shù)，例如1.那么必須保證左邊都小于它，右邊都大于它。也就是2和3必須在它右邊，而沒(méi)有比1小的數(shù)，因此左子樹為空
3. 因此，當(dāng)我們選中j作為根結(jié)點(diǎn)后，它左邊有j-1個(gè)數(shù)，右邊有i-j個(gè)數(shù)。左邊j-1個(gè)數(shù)可以構(gòu)造dp[j-1]個(gè)不同二叉搜索樹。右邊i-j個(gè)數(shù)可以構(gòu)造dp[i-j]個(gè)二叉搜索樹。
4. 當(dāng)我們j的右邊固定不變時(shí)，左邊每變一次，都是一課全新二叉搜索樹。同理，左邊不變，右邊變，也一樣。所以他倆是相乘的關(guān)系。也就是以j為根節(jié)點(diǎn)，有dp[j-1] * dp[i-j]種不同二叉搜索樹。
5. 而當(dāng)i = 3，我們有①，②，③這3個(gè)結(jié)點(diǎn)，j可以選擇任意一個(gè)作為根結(jié)點(diǎn)，所以每種情況都得考慮，因此j = ① 和 j = ② 和 j = ③這3種情況的和才是dp[i]的值。故：F[i] = F[1-1] * F[i-1] + F[2-1] * F[i-2] + F[3-1] * F[i-3] + … + F[i-1] * F[i-i]

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

4. 數(shù)組遍歷順序(單重循環(huán)，無(wú)需考慮遍歷順序，一共就一維，哪里來(lái)的誰(shuí)先誰(shuí)后)
5. 打印dp數(shù)組（自己生成dp數(shù)組后，將dp數(shù)組輸出看看，是否和自己預(yù)想的一樣。）

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-809945.html

class Solution {
    public int numTrees(int n) {
        int dp[] = new int[n+1];//需要0到n的下標(biāo)范圍，因此需要n+1個(gè)元素
        dp[0] = dp[1] = 1;//0個(gè)結(jié)點(diǎn)和1個(gè)結(jié)點(diǎn)，只有一種擺放方式
        for(int i = 2;i<=n;i++){//剩下的，需要將不同結(jié)點(diǎn)作為根結(jié)點(diǎn)的情況加起來(lái)
            for(int j = 1;j<=i;j++){//j表示當(dāng)前用誰(shuí)當(dāng)根結(jié)點(diǎn)
                dp[i]+=dp[j-1]*dp[i-j];//j當(dāng)根結(jié)點(diǎn)，左邊有j-1個(gè)元素，右邊有i-j個(gè)元素
            }
        }
        return dp[n];//返回n個(gè)結(jié)點(diǎn)可以構(gòu)成多少種二叉搜索樹
    }
}

到了這里，關(guān)于java數(shù)據(jù)結(jié)構(gòu)與算法刷題-----LeetCode96. 不同的二叉搜索樹的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！