目錄

動態規劃dp算法原理

力扣1137. 第 N 個泰波那契數

解析代碼1

解析代碼2

---

動態規劃dp算法原理

????????動態規劃（Dynamic Programming）算法的核心思想是：將大問題劃分為小問題進行解決，從而一步步獲取最優解的處理算法

????????動態規劃算法與分治算法類似，其基本思想也是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。

????????與分治法不同的是，適合于用動態規劃求解的問題，經分解得到的子問題往往不是互相獨立的（即下一個子階段的求解是建立在上一個子階段的解的基礎上）。

（除此斐波那契dp外還有其它類型的dp在后面會更新。）

動態規劃算法解決問題的分類：

計數	有多少種方式走到右下角?/?有多少種方法選出k個數使得和是sum
求最大值/最小值	從左上角走到右下角路徑的最大數字和最長上升子序列長度
求存在性	取石子游戲,先手是否必勝 /?能不能取出k? 個數字使得和是 sum

動態規劃dp算法一般步驟：

1. 確定狀態表示（dp[ i ] 表示什么，一般以 i 位置為起點或結尾分析，化成子問題）
2. 狀態轉移方程（斐波那契數列的狀態轉移方程為：dp[i] = dp[i-1] + dp[i-2]）
3. 初始化（斐波那契數列初始化可以為dp[0] = 0, dp[1] = 1;）
4. 填表順序（斐波那契數列從左往右填）
5. 返回值（如果斐波那契數列要求是第 n 個斐波那契數，返回dp[ n ] 即可）

---

力扣1137. 第 N 個泰波那契數

1137. 第 N 個泰波那契數

難度 簡單

泰波那契序列?Tn?定義如下：?

T0?= 0, T1?= 1, T2?= 1, 且在 n >= 0?的條件下 Tn+3?= Tn?+ Tn+1?+ Tn+2

給你整數?n，請返回第 n 個泰波那契數?Tn?的值。

示例 1：

輸入：n = 4
輸出：4
解釋：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

示例 2：

輸入：n = 25
輸出：1389537

提示：

• 0 <= n <= 37
• 答案保證是一個 32 位整數，即?answer <= 2^31 - 1。

class Solution {
public:int tribonacci(int n) {}
};

---

解析代碼1

簡單的DP，根據題目已經得到狀態轉移方程了：

class Solution {
public:int tribonacci(int n) {if(n <= 1) // 處理邊界return n;vector<int> dp(n+1, 0);dp[1] = dp[2] = 1;for(int i = 3; i <= n; ++i){dp[i] = dp[i-1] + dp[i-2] + dp[i-3];}return dp[n];}
};

---

解析代碼2

????????滾動數組對解法1進行空間上的優化，后面類似的空間優化就不寫了，因為筆試沒用，面試能講出來就行。

class Solution {
public:int tribonacci(int n) {if(n <= 1) // 處理邊界return n;int a = 0, b = 1, c = 1, d = 1; // 滾動數組思想優化空間for(int i = 3; i <= n; ++i){d = a + b + c;a = b;b = c;c = d;}return d;}
};