Title address

Leetcode 746. Climb stairs with minimum cost

Title Description

Give you an integer array cost, where cost[i] is the cost of climbing up the ith step of the stairs. Once you pay this fee, you can choose to climb up one or two steps.

You can choose to climb the stairs from the steps with subscript 0 or subscript 1.

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

Example 1:

Input: cost = [10,15,20]
Output: 15
Explanation: you will start with a step with a subscript of 1.

• Pay 15 and climb two steps up to the top of the stairs.
  The total cost is 15.
  Example 2:

Input: cost = [1100,1,1,1100,1,1100,1]
Output: 6
Explanation: you will start with a step with a subscript of 0.

• Pay 1 and climb up two steps to the step with subscript 2.
• Pay 1 and climb up two steps to the step with subscript 4.
• Pay 1, climb two steps up to the step with subscript 6.
• Pay 1 and climb up one step to the step with subscript 7.
• Pay 1, climb two steps up to the step with subscript 9.
• Pay 1, climb one step up to the top of the stairs.
  The total cost is 6.

Tips:

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

Problem solving ideas

  from the question, we need to get the minimum physical cost we need to pay to reach the top of the stairs. After paying the corresponding expenses, we can choose to go up two steps or one step.

   the optimal solution at this time is the minimum value of one of the two steps. At this time, the minimum cost of reaching the step is the minimum cost of the previous step plus the optimal solution of this step is the minimum cost.

   there are two recurrence formulas:

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

   in the recurrence formula, we need to know the values of dp[i - 1] and dp[i - 2], that is, the minimum cost of the first two steps of the ladder.
That is, if i is at least equal to 2, the initialization of the first and second steps is required.
  dp[0] = cost[0];

  dp[1] = cost[1];

  dp[2] = Math.min(dp[0],dp[1]) + cost[2];

  ...

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

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

It should be noted that at this time, DP [DP. Length - 1], that is, the last number of DP array, is not necessarily the minimum cost, because we can span one or two steps at a time, that is, the minimum value is math min(dp[dp.length - 1], dp[dp.length - 2])

code implementation

Method 1: dynamic programming

    // Dynamic programming method 1: use dp array to record the minimum physical strength required for each step
    public int minCostClimbingStairs(int[] cost) {
        if (cost.length == 1) {
            return cost[0];
        }

        // Define dp array
        int[] dp = new int[cost.length];

        // Initialize dp array
        dp[0] = cost[0];
        dp[1] = cost[1];
        // Recurrence formula: DP [i] = math min(dp[i - 1],dp[i - 2]) + cost[i];

        // dp[i]: the minimum cost to reach the i-th step
        for (int i = 2; i < dp.length; i++) {
            dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
        }
        return Math.min(dp[dp.length - 1], dp[dp.length - 2]);
    }

Complexity analysis:

• Time complexity: O(n)
• Space complexity: O(n)

Method 2: dynamic programming (optimized version)

    // Dynamic programming method 2: optimize dp array
    public int minCostClimbingStairs2(int[] cost) {
        if (cost.length == 1) {
            return cost[0];
        }

        // Define dp array
        int[] dp = new int[2];

        // Initialize dp array
        dp[0] = cost[0];
        dp[1] = cost[1];
        // Recurrence formula: DP [1] = math min(num,dp[0]) + cost[i];

        // dp[i]: the minimum cost to reach the i-th step
        for (int i = 2; i < cost.length; i++) {
            int num = dp[0];
            dp[0] = dp[1];
            dp[1] = Math.min(num, dp[0]) + cost[i];
        }
        return Math.min(dp[0], dp[1]);
    }

Complexity analysis:

• Time complexity: O(n)
• Space complexity: O(1)