509. 斐波那契數 - 力扣（LeetCode）

class Solution {
public:int fib(int n) {if(n==0){return 0;}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];}
};

70. 爬樓梯 - 力扣（LeetCode）

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. 使用最小花費爬樓梯 - 力扣（LeetCode）

class Solution {
public: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;i++){dp[i]+=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);}return dp[n];}
};

總結

理解dp

數組的定義，它代表什么很重要。初始化，需要考慮清楚。遞推公式需要理解