LeetCode746. Min Cost Climbing Stairs

本文介绍: 【代码】Lee tCo de746. Min Cos t Cli m bing St ai rs。

文章 目录

- 一、题目
- 二、题解

一、题目

You ar e g i v en an integer array cost where cost[i] i s the cost of i th step on a sta i r case. Once y ou p a y the cost, y ou can ei ther cli mb one o r two step s.

You can either start fro m the step with index 0, or the step with index 1.

Return the mini mum cost to r each the top of the floor.

Ex ample 1:

Input: cost = [10,15,20]
Output: 15
Ex plan ation: You wi ll start at index 1.

Pay 15 and cli mb two step s to reach the top.
The total cost is 15.
Ex ample 2:

Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Ex planation: You will start at index 0.

Pay 1 and c li mb two step s to reach index 2.
Pay 1 and cli mb two step s to reach index 4.
Pay 1 and cli mb two steps to reach index 6.
Pay 1 and cli m b one ste p to reach index 7.
Pay 1 and cli m b two steps to reach index 9.
Pay 1 and cli m b one ste p to reach the top.
The total cost is 6.

Constrain ts:

2 <= cost.length <= 1000
0 <= cost[i] <= 999

二、题解

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