學習要點

1. 動態規劃正著推
2. 動態規劃倒著推
3. 理解遞歸
4. 在動態規劃與純遞歸的類比分析中體會兩者各自的特點

題目鏈接

????????746. 使用最小花費爬樓梯 - 力扣（LeetCode）

題目描述

解法1：動態規劃倒著推

// dp[i]--->從第i階樓梯到達樓頂最小花費int minCostClimbingStairs(vector<int>& cost) {// dp[i]--->從第i階樓梯到達樓頂最小花費int n = cost.size();vector<int> dp(n);dp[n-1] = cost[n-1];dp[n-2] = cost[n-2];for(int i = n-3;i>=0;i--){dp[i] = min(dp[i+1] , dp[i+2]) + cost[i];}return min(dp[0],dp[1]);}

解法2：動態規劃正著推

//dp[i]--->到達第i階樓梯的最小花費
int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();vector<int> dp(n + 1);dp[0] = 0;dp[1] = 0;for (int i = 2; i < (n + 1); i++){dp[i] = min((dp[i - 1] + cost[i - 1]), (dp[i - 2] + cost[i - 2]));}return dp[n];
}

解法分析

1. 兩種解法都是采用動態規劃思想去解決問題，也就是說采用動態規劃方法去解決問題時，不止一種思考方式
2. 動態規劃法去解決問題時，宏觀邏輯是，利用計算機的記憶，把每種情況都記住，然后一步步迭代，這次迭代的過程，依賴上次迭代的結果，上次迭代的結果被計算機存儲了。
3. 可以說動態規劃是在一步步的暴力窮舉，只有走了第一步，才能走好第二步。只有走了第二步，才能走好第三步
4. 動態規劃在記什么：在記狀態，你決定如何考慮狀態，就決定你要怎么走
5. 最好怎么考慮狀態：狀態最少的狀態，就是解決問題最好的狀態

解法3：純遞歸

// 純遞歸-->通過樣例259/285，超出時間限制int dfs(int n,vector<int>& cost){if(n == 0) return 0;if(n == 1) return 0;int num_1 = dfs(n-1,cost) + cost[n-1];int num_2 = dfs(n-2,cost) + cost[n-2];return min(num_1,num_2);}int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();int m1 = dfs(n-1,cost) + cost[n-1];int m2 = dfs(n-2,cost) + cost[n-2];return min(m1,m2);}

動態規劃與遞歸類比

1. 兩者都是從最小或者說最直接的問題開始進行處理，一步步處理問題，達到最終目的
2. 動態規劃的問題處理過程是指定迭代結構，時間復雜度為O(n)
3. 遞歸的問題處理過程是遞歸樹結構，有太多的重復計算，造成時間復雜度膨脹
4. 遞歸往往因為時間復雜度太高，而無法處理大范圍的動態規劃問題以及其它大范圍的問題
5. 遞歸能處理的問題，動態規劃未必能輕松處理。例如leetcode：21. 合并兩個有序鏈表-CSDN博客如果使用動態規劃，實在無從下手。