Welcome to Subscribe On Youtube
746. Min Cost Climbing Stairs
Description
You are given an integer array cost
where cost[i]
is the cost of i^{th}
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)$.

class Solution { public int minCostClimbingStairs(int[] cost) { int f = 0, g = 0; for (int i = 2; i <= cost.length; ++i) { int gg = Math.min(f + cost[i  2], g + cost[i  1]); f = g; g = gg; } return g; } }

class Solution { public: int minCostClimbingStairs(vector<int>& cost) { int f = 0, g = 0; for (int i = 2; i <= cost.size(); ++i) { int gg = min(f + cost[i  2], g + cost[i  1]); f = g; g = gg; } return g; } };

class Solution: def minCostClimbingStairs(self, cost: List[int]) > int: f = g = 0 for i in range(2, len(cost) + 1): f, g = g, min(f + cost[i  2], g + cost[i  1]) return g

func minCostClimbingStairs(cost []int) int { var f, g int for i := 2; i <= n; i++ { f, g = g, min(f+cost[i2], g+cost[i1]) } return g }

function minCostClimbingStairs(cost: number[]): number { let [f, g] = [0, 0]; for (let i = 2; i <= cost.length; ++i) { [f, g] = [g, Math.min(f + cost[i  2], g + cost[i  1])]; } return g; }

impl Solution { pub fn min_cost_climbing_stairs(cost: Vec<i32>) > i32 { let (mut f, mut g) = (0, 0); for i in 2..=cost.len() { let gg = std::cmp::min(f + cost[i  2], g + cost[i  1]); f = g; g = gg; } g } }