原题地址
https://leetcode.com/problems/min-cost-climbing-stairs/description/
题意
给定一个cost数组，cost[0]或cost[1]出发，一次走1步或2步，每到达一个元素都要加上对应的cost，求到达（或者直接超过）最后一个元素的最小cost。
思路
做过很多次的题目(其实刷这道题是为了让刷过的动态规划题的√连起来23333），不过还是没能一次写对，记录一下错的几个地方吧。
dp[i]表示到第i个元素的最小花费（本题i从0到n-1）
dp[0]和dp[1]是固定的，就分别是cost[0]和cost[1]，从i=2开始，递推方程是
dp[i] = cost[i] + min( dp[i-1], dp[i-2])
犯的错
- 一开始给dp[1]赋值的时候写成dp[1]=min(cost[0],cost[1])了。
- 一开始以为是刚好到达最后一个元素的最小cost，所以直接返回了dp[n-1]，不过错了，于是看了下题目给的例子，发现
cost = [10, 15, 20]
的cost是15，就是说越过最后一个元素或者刚好到达都行，于是改成返回min(dp[ n-1 ] , dp[ n-2 ])
代码
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
if(n==0) return 0;
if(n==1) return cost[0];
if(n==2) return min(cost[0],cost[1]);
int dp[n]; //dp[i],the min cost to reach i (indexed from 0)
for (int i = 0; i < n; i++) {
dp[i] = 0;
}
dp[0] = cost[0];
dp[1] = cost[1];
for (int i = 2; i < n; i++) {
dp[i]= cost[i]+min(dp[i-1],dp[i-2]);
}
return min(dp[n-1],dp[n-2]);
}
};
