Minimum-Cost Stair Climb
Problem
Each stair has a cost paid when you stand on it. You may start at index 0 or 1 and may step one or two stairs at a time. Reach (one past) the last stair with minimum total cost. dp[i] = cost[i] + min(dp[i−1], dp[i−2]).
Input
cost = [10, 15, 20]Output
15Start at index 1 (cost 15) and step two stairs.
def min_cost(cost):
n = len(cost)
dp = [0] * n
dp[0], dp[1] = cost[0], cost[1]
for i in range(2, n):
dp[i] = cost[i] + min(dp[i - 1], dp[i - 2])
return min(dp[-1], dp[-2])function minCost(cost) {
const n = cost.length;
const dp = new Array(n);
dp[0] = cost[0]; dp[1] = cost[1];
for (let i = 2; i < n; i++) dp[i] = cost[i] + Math.min(dp[i - 1], dp[i - 2]);
return Math.min(dp[n - 1], dp[n - 2]);
}class Solution {
public int minCost(int[] cost) {
int n = cost.length;
int[] dp = new int[n];
dp[0] = cost[0]; dp[1] = cost[1];
for (int i = 2; i < n; i++) dp[i] = cost[i] + Math.min(dp[i - 1], dp[i - 2]);
return Math.min(dp[n - 1], dp[n - 2]);
}
}int minCost(vector<int>& cost) {
int n = cost.size();
vector<int> dp(n);
dp[0] = cost[0]; dp[1] = cost[1];
for (int i = 2; i < n; i++) dp[i] = cost[i] + min(dp[i - 1], dp[i - 2]);
return min(dp[n - 1], dp[n - 2]);
}