746. Climb stairs with minimum cost

Address ：

Power button https://leetcode-cn.com/problems/min-cost-climbing-stairs/

subject ：

Give you an array of integers cost , among cost[i] It's from the stairs i The cost of climbing a step up . Once you pay this fee , You can choose to climb up one or two steps .

You can choose from the subscript to 0 Or subscript 1 The steps began to climb the stairs .

Please calculate and return the minimum cost to reach the top of the stairs .

Example 1：

Input ：cost = [10,15,20] Output ：15 explain ： You will subscript 1 The steps begin . - payment 15 , Climb up two steps , Get to the top of the stairs . The total cost is 15 .

Example 2：

Input ：cost = [1,100,1,1,1,100,1,1,100,1] Output ：6 explain ： You will subscript 0 The steps begin . - payment 1 , Climb up two steps , The arrival subscript is 2 The steps of . - payment 1 , Climb up two steps , The arrival subscript is 4 The steps of . - payment 1 , Climb up two steps , The arrival subscript is 6 The steps of . - payment 1 , Climb up a step , The arrival subscript is 7 The steps of . - payment 1 , Climb up two steps , The arrival subscript is 9 The steps of . - payment 1 , Climb up a step , Get to the top of the stairs . The total cost is 6 .

Tips ：

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

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/min-cost-climbing-stairs
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Ideas ：

This is  (LeetCode-70) climb stairs   A derivative version of , We use the idea of dynamic programming to deal with

1. The first i The cost of a step is dp[i]

2. The first i The next step is from i-1 perhaps i-2 Up the steps , That is to say

        dp[i-1] Add the cost of this step up           perhaps

        dp[i-2] Add the cost of this step up

3. Then the formula can be set as ：

        dp[i] = min(dp[i-1] + cost[i-1] ,  dp[i-2] + cost[i-2]);

4. Initial element settings

        dp[0] = 0; dp[1] = 0;

        These two are the initial stages , It hasn't started to go up yet , So there is no cost

The topic gives a range of expenses ：2 <= cost.length <= 1000

that dp[10001] That's all right.

Method 1 、 Dynamic programming

#define min(a,b) ( (a) < (b) ? (a) : (b) )

int minCostClimbingStairs(int* cost, int costSize){
    int i;
    int dp[1001]={0,0};

    for(i=2; i<=costSize; i++)
    {
        dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);
    }

    return dp[costSize];
}

See more brush notes