SimuVedaAlgorithms Lab Open in the lab

Dynamic programming / Beginner

Climbing Stairs Visualizer

Fill a table from the smallest case up. Each cell reuses cells you already filled, so nothing is computed twice.

Start the Climbing Stairs simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n)
Average timeO(n)
Worst timeO(n)
Extra spaceO(n)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Base cases: 1 way to stand at step 0 and 1 way to reach step 1.
  2. ways(2) = ways(1) + ways(0) = 1 + 1.
  3. ways(2) = 2.
  4. ways(3) = ways(2) + ways(1) = 2 + 1.
  5. ways(3) = 3.
  6. ways(4) = ways(3) + ways(2) = 3 + 2.
  7. ways(4) = 5.
  8. ways(5) = ways(4) + ways(3) = 5 + 3.
  9. ways(5) = 8.
  10. ways(6) = ways(5) + ways(4) = 8 + 5.
  11. ways(6) = 13.
  12. There are 13 ways to climb 6 stairs.

Try it with your own input →

1D DP: climbing stairs in Java, Python, C++, C and JavaScript

int climbStairs(int n) {
  int[] dp = new int[n + 1];
  dp[0] = 1; dp[1] = 1;
  for (int i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}
def climb_stairs(n):
    dp = [0] * (n + 1)
    dp[0] = dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]
int climbStairs(int n) {
  vector<int> dp(n + 1);
  dp[0] = 1; dp[1] = 1;
  for (int i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}
int climbStairs(int n) {
  int dp[n + 2];
  dp[0] = 1; dp[1] = 1;
  for (int i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}
function climbStairs(n) {
  const dp = new Array(n + 1).fill(0);
  dp[0] = 1; dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

In an interview

LeetCode 70, Climbing Stairs: you climb 1 or 2 steps at a time. How many ways reach the top? Same shape: 198 House Robber.

Only the last two cells are ever read, so you can replace the array with two variables for O(1) space.

More dynamic programming