做ic销售的各种网站友情链接交易网站

最简单的动态规划，甚至不需要动态规划就可以解决的问题。初始状态、递推公式都已经有了，这道题就很简单了。

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

dp数组的含义：到达i位置的花费为dp[i]
递推公式：dp[i-1]+cost[i-1]和dp[i-2]+cost[i-2]的最小值
初始化：dp[0]=dp[1]=0
遍历顺序：正序

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()];}
};

动态规划继续加油！