Min Cost Climbing Stairs

easy dp

Problem

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.

Inputcost = [10, 15, 20]

Output15

Start at index 1 (cost 15) and step two stairs.

cost (comma-separated)

def min_cost_climbing_stairs(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 minCostClimbingStairs(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 minCostClimbingStairs(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 minCostClimbingStairs(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]);
}

Explanation

You climb stairs paying the cost of each step you land on, and from a step you may move up one or two. We want the cheapest way to get past the top. The natural idea is to ask: what's the minimum total cost to reach each step?

Let dp[i] be the least cost to stand on step i (having paid cost[i]). Since you arrive at i from either i-1 or i-2, we take whichever was cheaper: dp[i] = cost[i] + min(dp[i-1], dp[i-2]).

The base cases are the two valid starting steps: dp[0] = cost[0] and dp[1] = cost[1]. The "top" is just past the last step, which you can reach from either of the last two steps, so the answer is min(dp[n-1], dp[n-2]).

Example: cost = [10, 15, 20]. dp[2] = 20 + min(15, 10) = 30. The answer is min(dp[2], dp[1]) = min(30, 15) = 15 — start at step 1 and stride two steps over the top.

Each dp value is computed once from two earlier ones, so this is a single O(n) sweep.

Time: O(n) Space: O(n)