1.整數拆分

代碼隨想錄

視頻講解：動態規劃，本題關鍵在于理解遞推公式！| LeetCode：343. 整數拆分_嗶哩嗶哩_bilibili

代碼：

class Solution {
public:int integerBreak(int n) {// dp[i] 拆分數字i所獲得的最大乘積為dp[i]vector<int> dp(n + 1,0);// 初始化dp[2] = 1;// 遞推公式for(int i = 3;i <= n; i++){for(int j = 1;j < i - 1; j++){dp[i] =max(dp[i], max(j * (i - j),j * dp[i - j]));}}return dp[n];}
};

?思路：

dp數組的含義：拆分數字i所獲得的最大乘積為dp[i]

dp數組的遞推公式：分為兩種情況，拆分為兩個數字，拆分為兩個以上的數字。因此，dp[i] =max(dp[i], max(j * (i - j),j * dp[i - j]))。

????????這里要強調的是：max函數里dp[i]是為了去記錄 之前遍歷j的不同數值時的 等號左邊的最終要求得的dp[i] 可能取到的最大值——通過不斷更新 dp[i] 的值，我們可以在動態規劃的過程中找到拆分數字 i 所獲得的最大乘積。也正是因為這種記錄歷史信息的方式，我們才能夠不斷地比較并選擇最優解，從而得到最終的結果。

dp數組的初始化：從dp[2]開始有意義，dp[2]初始化為1

遍歷順序：從左到右

2.不同的二叉搜索樹?

代碼隨想錄

視頻講解：動態規劃找到子狀態之間的關系很重要！| LeetCode：96.不同的二叉搜索樹_嗶哩嗶哩_bilibili

代碼：

class Solution {
public:int numTrees(int n) {// dp[i]表示i個節點組成的互不相同的二叉搜索樹的種類vector<int> dp(n + 1,0);// 初始化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];}
};

?思路：

dp數組的含義：dp[i]表示i個節點組成的互不相同的二叉搜索樹的種類

dp數組的遞推公式：確認好一個節點為根結點，dp[i]就等于 它的不同數目左右子樹的種類和的乘積 的總和。即dp[i] += dp[j - 1] * dp[i - j]

dp數組的初始化：

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

因此dp[0] = 1

遍歷順序：從左到右?

我在做這道題的時候，犯了兩個錯，一個是我忘記左右子樹的節點總數是i-1了，另一個是dp[i]對應著不同數目的左右子樹，因此它是取不同情況的總和數。