題目描述
給你一個整數數組 cost ，其中 cost[i] 是從樓梯第 i 個臺階向上爬需要支付的費用。一旦你支付此費用，即可選擇向上爬一個或者兩個臺階。

你可以選擇從下標為 0 或下標為 1 的臺階開始爬樓梯。

請你計算并返回達到樓梯頂部的最低花費。

代碼

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {/*dp[i]的含義：表示達到第i+1個臺階最小的花費(下標從0開始)推導公式：dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])初始化：dp[0] = 0, dp[1] = 0確定遍歷順序：從前向后*/vector<int> dp(cost.size() + 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()];}
};

優化

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {/*dp[i]的含義：表示達到第i+1個臺階最小的花費(下標從0開始)推導公式：dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])初始化：dp[0] = 0, dp[1] = 0確定遍歷順序：從前向后*/int a = 0, b = 0, sum = 0;for (int i = 2; i <= cost.size(); i++) {a = b;b = sum;sum = min(a + cost[i - 2],b + cost[i - 1]);}return sum;}
};