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
数组的定义,它代表什么很重要。初始化,需要考虑清楚。递推公式需要理解