原題地址
https://leetcode.com/problems/min-cost-climbing-stairs/description/
題意
給定一個(gè)cost數(shù)組凛驮，cost[0]或cost[1]出發(fā)，一次走1步或2步侵续，每到達(dá)一個(gè)元素都要加上對(duì)應(yīng)的cost，求到達(dá)（或者直接超過(guò)）最后一個(gè)元素的最小cost傀缩。
思路
做過(guò)很多次的題目(其實(shí)刷這道題是為了讓刷過(guò)的動(dòng)態(tài)規(guī)劃題的√連起來(lái)23333）友扰，不過(guò)還是沒能一次寫對(duì)批糟，記錄一下錯(cuò)的幾個(gè)地方吧。
dp[i]表示到第i個(gè)元素的最小花費(fè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])
犯的錯(cuò)
- 一開始給dp[1]賦值的時(shí)候?qū)懗蒬p[1]=min(cost[0],cost[1])了酷麦。
- 一開始以為是剛好到達(dá)最后一個(gè)元素的最小cost矿卑，所以直接返回了dp[n-1]，不過(guò)錯(cuò)了沃饶，于是看了下題目給的例子母廷，發(fā)現(xiàn)
cost = [10, 15, 20]
的cost是15轻黑，就是說(shuō)越過(guò)最后一個(gè)元素或者剛好到達(dá)都行，于是改成返回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]);
}
};
