746. Min Cost Climbing Stairs
Description
You are given an integer array cost
where cost[i]
is the cost of ith
step on a staircase. Once you pay the cost, you can either climb one or two steps.
You can either start from the step with index 0
, or the step with index 1
.
Return the minimum cost to reach the top of the floor.
Example 1:
Input: cost = [10,15,20] Output: 15 Explanation: You will start at index 1. - Pay 15 and climb two steps to reach the top. The total cost is 15.
Example 2:
Input: cost = [1,100,1,1,1,100,1,1,100,1] Output: 6 Explanation: You will start at index 0. - Pay 1 and climb two steps to reach index 2. - Pay 1 and climb two steps to reach index 4. - Pay 1 and climb two steps to reach index 6. - Pay 1 and climb one step to reach index 7. - Pay 1 and climb two steps to reach index 9. - Pay 1 and climb one step to reach the top. The total cost is 6.
Constraints:
2 <= cost.length <= 1000
0 <= cost[i] <= 999
Solutions
Solution 1: Dynamic Programming
We define $f[i]$ as the minimum cost required to reach the $i$th step, initially $f[0] = f[1] = 0$. The answer is $f[n]$.
When $i \ge 2$, we can directly reach the $i$th step from the $(i - 1)$th step using $1$ step, or reach the $i$th step from the $(i - 2)$th step using $2$ steps. Therefore, we have the state transition equation:
$$ f[i] = \min(f[i - 1] + cost[i - 1], f[i - 2] + cost[i - 2]) $$
The final answer is $f[n]$.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the cost
array.
We notice that $f[i]$ in the state transition equation is only related to $f[i - 1]$ and $f[i - 2]$. Therefore, we can use two variables $f$ and $g$ to alternately record the values of $f[i - 2]$ and $f[i - 1]$, which optimizes the space complexity to $O(1)$.
1 2 3 4 5 6 7 |
|
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 8 9 10 |
|
Solution 2
1 2 3 4 5 6 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 |
|
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|