# Leetcode 746. Climbing stairs with minimum cost (dynamic programming method and optimization solution)

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 = cost;

dp = cost;

dp = Math.min(dp,dp) + cost;

...

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;
}

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

// Initialize dp array
dp = cost;
dp = cost;
// 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;
}

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

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

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

### Complexity analysis:

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

Keywords: Algorithm leetcode Dynamic Programming