題目：509.斐波那契數

思路：

? ? ? ? 1.確定dp[i]含義：第i個斐波拉契數值為dp[i]

? ? ? ? 2.確定遞推公式：dp[i] = dp[i - 1] + dp[i - 2]

? ? ? ? 3.dp數組如何初始化：d[0] = 1, dp[1] = 1

? ? ? ? 4.遍歷順序：從前向后

? ? ? ? 5.打印dp

class Solution {
public:int fib(int n) {if(n <= 1) return n;         //這一個返回值不能少，如果測試集n = 0,少了這一步后面dp[1]會越界vector<int> dp(n + 1);dp[0] = 0;dp[1] = 1;for(int i = 2; i <= n; i++){dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
};

只維護兩個值的方法如下

class Solution {
public:int fib(int n) {if(n <= 1) return n;         //這一個返回值不能少，如果測試集n = 0,少了這一步后面dp[1]會越界vector<int> dp(2);dp[0] = 0;dp[1] = 1;int sum;for(int i = 2; i <= n; i++){sum = dp[0] + dp[1];dp[0] = dp[1];dp[1] = sum;}return sum;}
};

題目：70.爬樓梯

思路：

? ? ? ? 舉個例子：想要買走到第5階，要么從第3階臺階邁兩步走到，要么從第4階臺階邁一步走到。所以dp[5] = dp[4] + dp[3].

1.dp數組含義：dp[i]代表到達第i階臺階有dp[i]種方法。

2.遞推關系：dp[i]? = dp[i -1] + dp[i - 2]

3.dp數組初始化：dp[1] = 1, dp[2] = 2

4.遍歷順序：從前向后

5.打印dp數組

代碼如下 ：

class Solution {
public:int climbStairs(int n) {if(n == 1) return 1;vector<int> dp(n + 1);dp[1] = 1;dp[2] = 2;for(int i = 3; i <= n; i++){dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
};

題目：746.用最小花費爬樓梯

1.dp數組含義：到達第i階樓梯要花費的體力為dp[i]

2.動態轉移方程：dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] = cost[i - 2])

3.初始化：dp[0] = 0, dp[1] = 0

4.遍歷順序

5.打印dp

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size() + 1;vector<int> dp(n);dp[0] = 0;dp[1] = 0;for(int i = 2; i < n; i++){dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);}return dp[n - 1];}
};