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 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)$.

Solution 2: Dynamic Programming

We define $f[i]$ as the minimum cost needed to reach the $i$-th stair. Initially, $f[0] = f[1] = 0$, and the answer is $f[n]$.

When $i \ge 2$, we can reach the $i$-th stair directly from the $(i - 1)$-th stair with one step, or from the $(i - 2)$-th stair with two steps. Therefore, we have the state transition equation:

\[f[i] = \min(f[i - 1] + \textit{cost}[i - 1], f[i - 2] + \textit{cost}[i - 2])\]

The final answer is $f[n]$.

The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the length of the array $\textit{cost}$.

Solution 3: Dynamic Programming (Space Optimization)

We notice that the state transition equation for $f[i]$ only depends on $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]$, thus optimizing the space complexity to $O(1)$.

Solution 4: Dynamic Programming

Thinking

Expanding every one-step and two-step choice is exponential. There can be $1000$ stairs, and the first call always moves to the next stair, so the chain has depth $n$. The cost of leaving stair $i$ depends only on $i+1$ and $i+2$, and past the top the cost is $0$. Set $f[i] = \textit{cost}[i] + \min(f[i+1], f[i+2])$ and fill $i$ from $n-1$ down to $0$. The answer is $\min(f[0], f[1])$.

We let $f[i]$ be the minimum cost of climbing from stair $i$ to the top. When $i \ge n$, $f[i] = 0$. For $i < n$,

\[f[i] = \textit{cost}[i] + \min(f[i + 1], f[i + 2])\]

Compute this for $i$ from $n - 1$ down to $0$. The answer is $\min(f[0], f[1])$.

The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the length of $\textit{cost}$.

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


// Solution 2
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] f = new int[n + 1];
        for (int i = 2; i <= n; ++i) {
            f[i] = Math.min(f[i - 2] + cost[i - 2], f[i - 1] + cost[i - 1]);
        }
        return f[n];
    }
}



// Solution 3
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;
    }
}



// Solution 4
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] f = new int[n + 2];
        for (int i = n - 1; i >= 0; --i) {
            f[i] = cost[i] + Math.min(f[i + 1], f[i + 2]);
        }
        return Math.min(f[0], f[1]);
    }
}


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


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



// Solution 3
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;
    }
};



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


  • 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


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



# Solution 3
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



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


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


// Solution 2
func minCostClimbingStairs(cost []int) int {
	n := len(cost)
	f := make([]int, n+1)
	for i := 2; i <= n; i++ {
		f[i] = min(f[i-1]+cost[i-1], f[i-2]+cost[i-2])
	}
	return f[n]
}



// Solution 3
func minCostClimbingStairs(cost []int) int {
	var f, g int
	for i := 2; i <= n; i++ {
		f, g = g, min(f+cost[i-2], g+cost[i-1])
	}
	return g
}



// Solution 4
func minCostClimbingStairs(cost []int) int {
	n := len(cost)
	f := make([]int, n+2)
	for i := n - 1; i >= 0; i-- {
		f[i] = cost[i] + min(f[i+1], f[i+2])
	}
	return min(f[0], f[1])
}


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


// Solution 2
function minCostClimbingStairs(cost: number[]): number {
    const n = cost.length;
    const f: number[] = Array(n + 1).fill(0);
    for (let i = 2; i <= n; ++i) {
        f[i] = Math.min(f[i - 1] + cost[i - 1], f[i - 2] + cost[i - 2]);
    }
    return f[n];
}



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



// Solution 4
function minCostClimbingStairs(cost: number[]): number {
    const n = cost.length;
    const f: number[] = Array(n + 2).fill(0);
    for (let i = n - 1; i >= 0; --i) {
        f[i] = cost[i] + Math.min(f[i + 1], f[i + 2]);
    }
    return Math.min(f[0], f[1]);
}


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


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



// Solution 3
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
    }
}



// Solution 4
impl Solution {
    pub fn min_cost_climbing_stairs(cost: Vec<i32>) -> i32 {
        let n = cost.len();
        let mut f = vec![0; n + 2];
        for i in (0..n).rev() {
            f[i] = cost[i] + f[i + 1].min(f[i + 2]);
        }
        f[0].min(f[1])
    }
}


  • function minCostClimbingStairs(cost) {
    const n = cost.length;
    const f = Array(n).fill(-1);
    const dfs = i => {
        if (i >= n) {
            return 0;
        }
        if (f[i] < 0) {
            f[i] = cost[i] + Math.min(dfs(i + 1), dfs(i + 2));
        }
        return f[i];
    };
    return Math.min(dfs(0), dfs(1));
}


// Solution 2
function minCostClimbingStairs(cost) {
    const n = cost.length;
    const f = Array(n + 1).fill(0);
    for (let i = 2; i <= n; ++i) {
        f[i] = Math.min(f[i - 1] + cost[i - 1], f[i - 2] + cost[i - 2]);
    }
    return f[n];
}



// Solution 3
function minCostClimbingStairs(cost) {
    let [f, g] = [0, 0];
    for (let i = 1; i < cost.length; ++i) {
        [f, g] = [g, Math.min(f + cost[i - 1], g + cost[i])];
    }
    return g;
}



// Solution 4
function minCostClimbingStairs(cost) {
    const n = cost.length;
    const f = Array(n + 2).fill(0);
    for (let i = n - 1; i >= 0; --i) {
        f[i] = cost[i] + Math.min(f[i + 1], f[i + 2]);
    }
    return Math.min(f[0], f[1]);
}

All Problems

All Solutions