?个人主页: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()];
}
};