Min Cost Climbing Stairs

EasyDynamic ProgrammingArray
Category: 1-D Dynamic Programming
Companies that ask this question:
AmazonGoogleMicrosoft

Approach

Min Cost Climbing Stairs

Problem Description

You are given an integer array cost where cost[i] is the cost of the 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.

Approach

This is a classic dynamic programming problem similar to Climbing Stairs, but with costs involved.

Key Insights

  1. State Definition: dp[i] = minimum cost to reach step i
  2. Base Cases:
    • dp[0] = cost[0] (start at step 0)
    • dp[1] = cost[1] (start at step 1)
  3. Recurrence Relation: dp[i] = cost[i] + min(dp[i-1], dp[i-2])
  4. Final Answer: min(dp[n-1], dp[n-2]) since we can reach the top from either the last or second-to-last step

Algorithm

  1. Initialize DP array with base cases
  2. For each step from 2 to n-1, calculate the minimum cost to reach it
  3. Return the minimum of the last two steps

Complexity Analysis

  • Time Complexity: O(n) - single pass through the array
  • Space Complexity: O(n) for DP array, can be optimized to O(1) using two variables

Solution

java
1class Solution {
2    public int minCostClimbingStairs(int[] cost) {
3        int n = cost.length;
4
5        // dp[i] represents the minimum cost to reach step i
6        int[] dp = new int[n];
7        dp[0] = cost[0];
8        dp[1] = cost[1];
9
10        // For each step, we can come from either the previous step or two steps back
11        for (int i = 2; i < n; i++) {
12            dp[i] = cost[i] + Math.min(dp[i-1], dp[i-2]);
13        }
14
15        // We can step off from either the last or second-to-last step
16        return Math.min(dp[n-1], dp[n-2]);
17    }
18}
19
Loading visualizer...