代码随想录32_动态规划基础

理论基础

Dynamic Programming,当前状态由上一状态推导而来。

FIB 斐波那契

1.初始化数组的时候需要分配数组大小；
2.如果没有分配，使用push_back是安全的；

题解

class Solution {
public:int fib(int n) {if(n<=1) return n;// vector<int> dp(n+1);// dp[0]=0;// dp[1]=1;vector<int> dp;dp.push_back(0);dp.push_back(1);for(int i=2;i<=n;i++){dp.push_back(dp[i-1]+dp[i-2]);//dp[i]=dp[i-1]+dp[i-2];}return dp[n];}
};

使用最小花费爬楼梯

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