Min Cost Climbing Stairs
Easy About 10 min Free, no account needed
Pay each step you land on; reach the top as cheaply as possible.
The brief
cost[i] is the toll for stepping on stair i. After paying you may climb
1 or 2 stairs. You may start at stair 0 or 1; return the cheapest
total to step past the last stair.
The obvious approach recurses on both possible moves, 2^n. The hidden staircase has 200,000 steps, so the exponential branching is far too slow. You will need an approach closer to O(n).
Starter code
using System;
public class Solution
{
// TODO: return the cheapest cost to step past the last stair (start at 0 or 1).
public long MinCostClimbingStairs(int[] cost)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Dynamic programming
- Define subproblems and a recurrence, then reuse solved subproblems instead of recomputing them.
Do these first
Related katas
- Counting Bits Easy Free Popcounts for 0..n - reuse the table you are already building.
- House Robber Easy Free Maximize the loot without robbing two adjacent houses.
- Unique Paths Easy Free Count the robot's lattice paths across the grid.
- Coin Change (Fewest Coins) Medium Free The fewest coins that make the amount, or -1.