I punch simple algorithm questions | leetcode. [746] use minimum cost climb stairs – JAVA

This is the fourth day of my participation in Gwen Challenge

The original problem

Use stairs at minimal cost

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.

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

The sample? 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

jolt

This is still labeled dynamic programming, so we’re going to follow the basics.

First of all, I looked at the problem carefully, and at first glance it looked like climbing stairs, but one of the big changes was that it was physically exhausting on each step, so when we did the calculation, we had to judge the energy expenditure on each step, and we had to figure out how to get to the end point, at the lowest cost.

• The boundary conditions

  According to the problem, there is no obvious boundary judgment, that is, it needs to be added in the process of solving the problem.

• subproblems

  Based on previous experience, we might start by setting the subproblem as dp[n] in order to reach order n.

  However, it is difficult to infer DP [n] through DP [n-1] by using the draft calculus, so we need to find another method. After looking at the problem, we can find that we can take one step or climb two steps at a time, and then we can think from the top to the beginning, depending on the last step or climb two steps, and then reset the sub-problem, divided into:

  Dp [n] [0] is the last step and DP [n] [1] is the last step.

  And then since they specify that there are at least two steps, we can reset our boundary conditions

  
  $$dp(n)=\left\{ \begin{aligned} prices[1][0]=0,prices[1][1]=0 & &\ n = 1 \\ prices[2][0]=cost[1],prices[2][1]=cost[0] & &\ n = 2 \\ \end{aligned} \right.$$

• equation

  According to the previous paragraph, we should judge the consumption of the two moves in each step to the next step, take the smallest one each time, and then add the consumption of the first or second step to the next step, so we can get the following:

  
  $$dp(n)=\left\{ \begin{aligned} prices[1][0]=0,prices[1][1]=0 & &\ n = 1 \\ prices[2][0]=cost[1],prices[2][1]=cost[0] & &\ n = 2 \\ dp[n][0] = cost[n – 1] + Math.min(dp[n – 1][0], dp[n – 1][1]); &&\ n >2; To go one step \ \ dp [n] [1] = cost [n – 2) + math.h min (dp [0], [n – 2] dp [n – 2] [1]). &&\ n >2; Go two steps \\ \end{aligned} \right.$$

  When cost[I] is done iterating, you get dp[n] and that’s what’s in the array

• Write code that combines conditions

    public int minCostClimbingStairs(int[] cost) {
        // Initializes a two-dimensional array
        int[][] dp = new int[cost.length + 1] [2];
		// Boundary conditions
        dp[1] [0] = 0;
        dp[1] [1] = 0;
        dp[2] [0] = cost[1];
        dp[2] [1] = cost[0];
        // Change the code according to the transfer equation
        for (int i = 3; i <= cost.length ; i++) {
            dp[i][0] = cost[i - 1] + Math.min(dp[i - 1] [0], dp[i - 1] [1]);
            dp[i][1] = cost[i - 2] + Math.min(dp[i - 2] [0], dp[i - 2] [1]);
        }
        return Math.min(dp[cost.length][0], dp[cost.length][1]);
    }
Copy the code

It then runs and finds that execution time beats 99.84% and memory beats 97.12%

The results are good, this is obviously spatially optimized, there is a lot of double computation on each branch, and it is possible to replace multiple two-dimensional arrays with several variables. Because of laziness, so touch the fish 🦑.

closed

• The subproblem setting of dynamic programming is very important. A good subproblem can greatly reduce the complexity