Problem Statement:
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 <= 10000 <= cost[i] <= 999
Approach:
- Subproblem definition:
Let dp[i]= minimum cost to reach step i. - Best Case:
To stand before the staircase:
dp[0] = 0, dp[1] = 0(since you can start at step 0 or step 1 for free). - Transition relation
- To reach step
i, you could:-
Come from
i-1 â pay dp[i-1] + cost[i-1]. -
Come from
i-2 â pay dp[i-2] + cost[i-2]. - So,
dp[i]=min(dp[iâ1]+cost[iâ1], dp[iâ2]+cost[iâ2]).
-
Come from
- The result is dp[n] (minimum cost to step just beyond the last stair).
Time & Space Complexity:
Time Complexity: O(n)
Space Complexity: O(1)
Dry Run
Input: n = 5
Step 0: Start Function: climbStairs(5) n = 5 dp = [0, 1, 2] // base cases Iteration (i = 3): - dp[3] = dp[2] + dp[1] = 2 + 1 = 3 - dp = [0, 1, 2, 3] Iteration (i = 4): - dp[4] = dp[3] + dp[2] = 3 + 2 = 5 - dp = [0, 1, 2, 3, 5] Iteration (i = 5): - dp[5] = dp[4] + dp[3] = 5 + 3 = 8 - dp = [0, 1, 2, 3, 5, 8] Loop ends (i > n) Step 3: End Return dp[5] = 8
Output: 8
Visualisation:
var climbStairs = function(n) {
let dp = [0, 1, 2];
for (let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
};
from typing import List
def minCostClimbingStairs(cost: List[int]) -> int:
n = len(cost)
dp = [0, 0]
for i in range(2, n + 1):
dp.append(min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]))
return dp[n]
class Solution {
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
int[] dp = new int[n + 1];
dp[0] = dp[1] = 0;
for (int i = 2; i <= n; i++) {
dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[n];
}
}
#include <vector>
#include <algorithm>
using namespace std;
int minCostClimbingStairs(vector& cost) {
int n = cost.size();
vector dp(n + 1, 0);
dp[0] = dp[1] = 0;
for (int i = 2; i <= n; i++) {
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[n];
}
#include <stdio.h>
#include <stdlib.h>
int minCostClimbingStairs(int* cost, int n) {
int* dp = (int*)calloc(n + 1, sizeof(int));
dp[0] = dp[1] = 0;
for (int i = 2; i <= n; i++) {
int option1 = dp[i - 1] + cost[i - 1];
int option2 = dp[i - 2] + cost[i - 2];
dp[i] = option1 < option2 ? option1 : option2;
}
int result = dp[n];
free(dp);
return result;
}
using System;
using System.Collections.Generic;
public class Solution {
public int MinCostClimbingStairs(int[] cost) {
int n = cost.Length;
int[] dp = new int[n + 1];
dp[0] = dp[1] = 0;
for (int i = 2; i <= n; i++) {
dp[i] = Math.Min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[n];
}
}
