[TOC] ## 概述 - 首先，動態規劃問題的一般形式就是求最值 - 求解動態規劃的核心問題是窮舉 - 動態規劃的窮舉有點特別，因為這類問題存在「重疊子問題」，如果暴力窮舉的話效率會極其低下，所以需要「備忘錄」或者「DP table」來優化窮舉過程，避免不必要的計算 - 動態規劃問題一定會具備「最優子結構」，才能通過子問題的最值得到原問題的最值 - 正確的「狀態轉移方程」才能正確地窮舉 寫出狀態轉移方程是最困難的，狀態轉移方程思考 `明確 base case -> 明確「狀態」-> 明確「選擇」 -> 定義 dp 數組/函數的含義` ## 斐波那契數列 ### 暴力遞歸 ``` int fib(int N) { if (N == 1 || N == 2) return 1; return fib(N - 1) + fib(N - 2); } ``` 假設值為20 ,則如圖效率非常的低  遞歸算法的時間復雜度怎么計算？ - 就是用子問題個數乘以解決一個子問題需要的時間。 - 首先計算子問題個數，即遞歸樹中節點的總數。顯然二叉樹節點總數為指數級別，所以子問題個數為 O(2^n)。 然后計算解決一個子問題的時間，在本算法中，沒有循環，只有 f(n - 1) + f(n - 2) 一個加法操作，時間為 O(1)。 所以，這個算法的時間復雜度為二者相乘，即 O(2^n)，指數級別，爆炸 算法低效的原因? - 存在大量重復計算，比如 f(18) 被計算了兩次，而且你可以看到，以 f(18) 為根的這個遞歸樹體量巨大，多算一遍，會耗費巨大的時間。更何況，還不止 f(18) 這一個節點被重復計算，所以這個算法及其低效。 這就是動態規劃問題的第一個性質：重疊子問題 ### 帶備忘錄的遞歸解法 ``` func fib(n int) int { if n <= 2 { return 1 } mem := make([]int, n, n) return helper(n, mem) } func helper(n int, men []int) int { if n <= 2 { return 1 } if i := men[n-1]; i != 0 { return i } men[n-1] = helper(n-1, men) + helper(n-2, men) return men[n-1] } ```  帶「備忘錄」的遞歸算法，把一棵存在巨量冗余的遞歸樹通過「剪枝」，改造成了一幅不存在冗余的遞歸圖，極大減少了子問題（即遞歸圖中節點）的個數  時間復雜度 - 即圖中節點的總數，由于本算法不存在冗余計算，子問題就是 f(1), f(2), f(3) ... f(20)，數量和輸入規模 n = 20 成正比，所以子問題個數為 O(n)。 解決一個子問題的時間，同上，沒有什么循環，時間為 O(1)。 所以，本算法的時間復雜度是 O(n)。比起暴力算法，是降維打擊 ### dp 數組的迭代解法 ``` int fib(int N) { vector<int> dp(N + 1, 0); // base case dp[1] = dp[2] = 1; for (int i = 3; i <= N; i++) dp[i] = dp[i - 1] + dp[i - 2]; return dp[N]; } ```  「狀態轉移方程」  你把 f(n) 想做一個狀態 n，這個狀態 n 是由狀態 n - 1 和狀態 n - 2 相加轉移而來，這就叫狀態轉移