【LeetCode】746. 使用最小花費爬樓梯（C++）

746. 使用最小花費爬樓梯

• ​​1 題目描述​​
• ​​2 示例描述​​

• ​​2.1 示例1​​
• ​​2.2 示例2​​

• ​​3 解題提示​​
• ​​4 解題思路​​
• ​​5 代碼詳解​​

1 題目描述

數組的每個下标作為一個階梯，第 i 個階梯對應着一個非負數的體力花費值 cost[i]（下标從 0 開始）。

每當你爬上一個階梯你都要花費對應的體力值，一旦支付了相應的體力值，你就可以選擇向上爬一個階梯或者爬兩個階梯。

請你找出達到樓層頂部的最低花費。在開始時，你可以選擇從下标為 0 或 1 的元素作為初始階梯。

2 示例描述

2.1 示例1

輸入：cost = [10, 15, 20]

輸出：15

解釋：最低花費是從 cost[1] 開始，然後走兩步即可到階梯頂，一共花費 15 。

2.2 示例2

輸入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]

輸出：6

解釋：最低花費方式是從 cost[0] 開始，逐個經過那些 1 ，跳過 cost[3] ，一共花費 6 。

3 解題提示

4 解題思路

5 代碼詳解

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