动态规划--使用最小花费爬楼梯

 个人主页：Lei宝啊 

愿所有美好如期而遇

---

本体题目链接https://leetcode.cn/problems/GzCJIP/

示例图示

 

 

本题动态规划解释

动态规划，如果真要清楚理解的话，可能一开始学习不太可能，专有名词太多，我们就先简单理解。

状态表示，状态转移方程，初始化，填表顺序，返回值，也就分这么几个步骤，也许你不理解，那就对了，我们分开简单说。

状态表示，也就是建一个数组，我们叫做dp表(动态规划缩写)，数组每个值都对应一个状态，本题来说，dp[i]就表示到达第i个台阶的最低花费。我们如何得到他的状态，经验+题目分析(这不是废话嘛)，简单来说，多做题，上百道就差不多有感觉了(滑稽)。

状态转移方程，就是dp[i]等于什么，我们图示已然分析出来:

dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])。

初始化，给初始的几个状态赋值。我们为了避免越界，给dp[1]和dp[0]赋初值0。

填表顺序，就是根据状态转移方程填dp表。

返回值，返回哪个位置的值呢？由你决定。

 

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