摘要

• 整數(shù)拆分和不同的二叉搜索樹，這兩個(gè)問題，都可以看做是從整體中不斷拆出子結(jié)構(gòu)（整數(shù)的子結(jié)構(gòu)是更小的整數(shù)，二叉樹的子結(jié)構(gòu)是子樹），模擬拆分子結(jié)構(gòu)的過程，有助于思考遞推公式。
• 這兩題都是從dp數(shù)組的初始已知的部分開始，用子結(jié)構(gòu)的dp數(shù)組去構(gòu)造答案的。

LeetCode343 整數(shù)拆分

343. 整數(shù)拆分 - 力扣（Leetcode）

• 確定dp數(shù)組及數(shù)組下標(biāo)的含義：

  • 對(duì)于一個(gè)正整數(shù)i，拆分為k個(gè)正整數(shù)，有很多種拆分方式，但應(yīng)該有唯一的一種拆分方式使得拆分出的k個(gè)正整數(shù)的乘積最大。先嘗試一維的dp數(shù)組，dp[i]為正整數(shù)i拆分為k個(gè)正整數(shù)的乘積的最大值。

• 確定遞推公式，還是先看簡(jiǎn)單的子問題

  • 當(dāng)n == 1時(shí)，1只有一種拆分方式，拆分成一個(gè)1,dp[1]顯然是1。
  • 當(dāng)n == 2時(shí)，2也只有一種拆分方式，拆分為兩個(gè)1，所以dp[2]也是1。
  • 當(dāng)n == 3時(shí)，3有兩種拆分方式，一是先拆出一個(gè)1，得到[1, 2]，二是再把2拆分成一個(gè)1，得到[1, 1, 1]。可以把dp[3]的求解過程看成是這兩種拆法的乘積的比較，即第一種是不把2繼續(xù)往下拆，第二種是把2繼續(xù)往下拆，寫成表達(dá)式應(yīng)該是dp[3]=max(1*(3-1), 1*dp[3-1])。
  • 當(dāng)n == i時(shí)，假如我們先只拆出一個(gè)正整數(shù)j，得到[j, i-j]。對(duì)于[j, i-j]這一狀態(tài)，要么j*(i-j)就是乘積的最大值，要么就還要繼續(xù)拆分i-j來得到乘積的最大值，而dp[i-j]是拆分i-j為·k個(gè)正整數(shù)的乘積的最大值。假設(shè)我們已經(jīng)知道了dp[i-j]的值，那么，對(duì)于拆出一個(gè)正整數(shù)j，dp[i]的值只可能是j*(i-j)和j*dp[i-j]中的較大值。
  • 對(duì)于n == i，如果我們遍歷所有可能的j，就可以得到dp[i]真正的最大值。

  

• 根據(jù)遞推公式，我們可以知道dp[0]、dp[1]、dp[2]的初始狀態(tài)。

• 由于我們先知道的是較小的正整數(shù)的dp值，所以遍歷方法應(yīng)該是i逐漸增大到n，j也應(yīng)該是從1逐漸增大到i。

題解代碼如下

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

• 實(shí)際上，j只需要遍歷到i / 2即可，因?yàn)楫?dāng)j > i / 2時(shí)，i - j就和之前j < i / 2的j的值重復(fù)了

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

LeetCode96 不同的二叉搜索樹

96. 不同的二叉搜索樹 - 力扣（Leetcode）

• 確定dp數(shù)組及數(shù)組下標(biāo)的含義：dp[i]是由i個(gè)節(jié)點(diǎn)組成，且節(jié)點(diǎn)值互不相同的二叉搜索樹的種數(shù)。

• 確定遞推公式，先看簡(jiǎn)單的子問題

  • 當(dāng)n == 0，即沒有節(jié)點(diǎn)時(shí)，樹為空樹，只有一種，dp[0]=1
  • 當(dāng)n == 1時(shí)，樹只有一個(gè)節(jié)點(diǎn)，所以也只有一種，dp[1]=1
  • 當(dāng)n == 2時(shí)，樹有兩個(gè)節(jié)點(diǎn)，有兩種情況：一是1作為根節(jié)點(diǎn)，二是2作為根節(jié)點(diǎn)，dp[2]=2
  • 當(dāng)n == 3時(shí)，可以這樣來考慮：
    1. 當(dāng)1作為根節(jié)點(diǎn)時(shí)，左子樹的節(jié)點(diǎn)數(shù)為0，右子樹的節(jié)點(diǎn)數(shù)為2，有dp[0]*dp[2]種可能。
    2. 當(dāng)2作為根節(jié)點(diǎn)時(shí)，左子樹的節(jié)點(diǎn)數(shù)為1，右子樹的節(jié)點(diǎn)數(shù)為1，有dp[1]*dp[1]種可能。
    3. 當(dāng)3作為根節(jié)點(diǎn)時(shí)，左子樹的節(jié)點(diǎn)數(shù)為2，右子樹的節(jié)點(diǎn)數(shù)為0，有dp[2]*dp[0]種可能。
  • 當(dāng)n == i時(shí)，設(shè)根節(jié)點(diǎn)的值為j，則左子樹的節(jié)點(diǎn)數(shù)為j - 1，右子樹的節(jié)點(diǎn)數(shù)為i - j。

  

• dp數(shù)組的初始值可以由遞推公式得到

• 由于我們先知道的是i較小的dp[i]，所以i應(yīng)該從小到大來構(gòu)造dp數(shù)組

題解代碼如下

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