“This is the fourth day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

The original link

746. Stair Climbing at minimal Cost – Force Buckle (LeetCode) (leetcode-cn.com)

Topic describes

Each subscript of the array is a ladder, and the ith ladder corresponds to a non-negative cost cost[I] (the subscript starts at 0).

Every time you climb a ladder you spend your stamina, and once you pay your stamina you can choose to climb one ladder or two.

Please find the lowest cost to reach the top of the floor. To start, you can choose to start with an element with subscript 0 or 1.

The test case

Example 1:

Input: cost = [10, 15, 20] Output: 15 Explanation: The lowest cost is to start at cost[1] and then walk two steps to the top of the ladder, which costs 15 in total.Copy the code

Example 2:

Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] Output: 6 Explanation: The lowest cost is to start at cost[0], pass through the ones one by one, skip cost[3], and cost 6 altogether.Copy the code

Parameter limits

  • costThe length range of theta is theta[2, 1000].
  • cost[i]It’s going to be an integer in the range of[0, 999] 。

Analysis of the

Reading the title, we can refine a few points:

  • Every flight of stairs was a physical struggle
  • When we stand on the NTH step, we can choose fromn-1Across the step ton; Or inn-2Across two stepsnThat’s the key state transition equation for dynamic programming in this problem
  • The final stage is physically demandingx“, but we need to step over and stand on the roof. Please be careful. The hidden condition here is that we actually need to step over the roof step not mentioned in the question, and the energy cost of this step is 0

They want us to calculate the minimum cost of physical effort, so f(n) = math.min (f(n-2), f(n-1)) + cost[n] when we stand on the NTH step.

code

var minCostClimbingStairs = function(cost) {
    cost.push(0)
    let arr = [cost[0],cost[1]].for(let i=2; i<cost.length; i++){ arr[i]=Math.min(arr[i-1],arr[i-2])+cost[i];
    }
    return arr.pop();
};
Copy the code

This code is a classic DP table calculation

To optimize the

Since we only need to pay attention to the data of F (n-2) and F (n-1) when calculating F (n), we can simplify the DP table into two variables A and B to store the values of F (n-2) and F (n-1)

var minCostClimbingStairs = function(cost) {
    cost.push(0)
    let [a,b] = [cost[0],cost[1]].let temp;
    for(let i=2; i<cost.length; i++){ temp = b; b=Math.min(a,b)+cost[i];
        a=temp;
    }
    return b;
};
Copy the code

Today’s force buckle brush problem share here, thank you for reading ~