Leetcode skimming: dynamic planning 03 (climb stairs with minimum cost)

746. Use the minimum cost to climb the stairs

Force button topic link

Each subscript of the array acts as a ladder , The first i A ladder corresponds to a non negative amount of physical expenditure cost[i]（ Subscript from 0 Start ）.

Every time you climb a ladder, you have to spend the corresponding stamina value , Once you've paid for your strength , You can choose to climb up one ladder or two .

Please find out the lowest cost to reach the top of the floor . At the beginning , You can choose from the subscript to 0 or 1 As the initial step .

Example 1：

Input ：cost = [10, 15, 20]
Output ：15
explain ： The minimum cost is from cost[1] Start , Then take two steps to the top of the steps , Total cost 15 .
Example 2：

Input ：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output ：6
explain ： The lowest cost way is from cost[0] Start , One by one through those 1 , skip cost[3] , Total cost 6 .

Tips ：

• cost The length range of is [2, 1000].
• cost[i] It's going to be an integer , The scope is [0, 999] .

Just think of this question dp The meaning of each layer , It's easy to do it
dp[i] For the minimum consumption of jumping out of the current layer .
dp[i]=dp[i-1]+dp[i-2]+cost[i]

package com.programmercarl.dynamic;


/** * @ClassName MinCostClimbingStairs * @Descriotion TODO * @Author nitaotao * @Date 2022/7/22 12:34 * @Version 1.0 * https://leetcode.cn/problems/min-cost-climbing-stairs/ * 746.  Use the minimum cost to climb the stairs  **/
public class MinCostClimbingStairs {
    
    public int minCostClimbingStairs(int[] cost) {
    
        // Choose two positions at a time and add the cheapest one in one step 
        // Jumping out of this level requires the least consumption 
        int[] dp = new int[cost.length];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < dp.length; i++) {
    
            // State transition equation 
            dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
        }
        return Math.min(dp[cost.length - 1], dp[cost.length - 2]);
    }

    public static void main(String[] args) {
    
        System.out.println(new MinCostClimbingStairs().minCostClimbingStairs(new int[]{
    0, 0, 1, 1}));
        System.out.println(new MinCostClimbingStairs().minCostClimbingStairs(new int[]{
    1,100,1,1,1,100,1,1,100,1}));
    }
}