Solution Staircase

Problem Statement

Given a stair with 'n' steps, implement a method to count how many possible ways are there to reach the top of the staircase, given that, at every step you can either take 1 step, 2 steps, or 3 steps.

Example 1:

Number of stairs (n) : 3
Number of ways = 4
Explanation: Following are the four ways we can climb : {1,1,1}, {1,2}, {2,1}, {3} 

Example 2:

Number of stairs (n) : 4
Number of ways = 7
Explanation: Following are the seven ways we can climb : {1,1,1,1}, {1,1,2}, {1,2,1}, {2,1,1}, 
{2,2}, {1,3}, {3,1}

Constraints:

• 1 <= n <= 45

Let's first start with a recursive brute-force solution.

Basic Solution

At every step, we have three options: either jump 1 step, 2 steps, or 3 steps. So our algorithm will look like this:

class Solution {

  public int countWays(int n) {
    if (n == 0) return 1; // base case, we don't need to take any step, so there is only one way

    if (n == 1) return 1; // we can take one step to reach the end, and that is the only way

    if (n == 2) return 2; // we can take one step twice or jump two steps to reach at the top

    // if we take 1 step, we are left with 'n-1' steps;
    int take1Step = countWays(n - 1);
    // similarly, if we took 2 steps, we are left with 'n-2' steps;
    int take2Step = countWays(n - 2);
    // if we took 3 steps, we are left with 'n-3' steps;
    int take3Step = countWays(n - 3);

    return take1Step + take2Step + take3Step;
  }

  public static void main(String[] args) {
    Solution sc = new Solution();
    System.out.println(sc.countWays(3));
    System.out.println(sc.countWays(4));
    System.out.println(sc.countWays(5));
  }
}

The time complexity of the above algorithm is exponential as we are making three recursive call in the same function. The space complexity is which is used to store the recursion stack.

Let's visually draw the recursion for CountWays(4) to see the overlapping subproblems:

We can clearly see the overlapping subproblem pattern: CountWays(2) and CountWays(1) have been called twice. We can optimize this using memoization.

Top-down Dynamic Programming with Memoization

We can use an array to store the already solved subproblems. Here is the code:

class Solution {

  public int countWays(int n) {
    int dp[] = new int[n + 1];
    return countWaysRecursive(dp, n);
  }

  public int countWaysRecursive(int[] dp, int n) {
    if (n == 0) return 1; // base case, we don't need to take any step, so there is only one way

    if (n == 1) return 1; // we can take one step to reach the end, and that is the only way

    if (n == 2) return 2; // we can take one step twice or jump two steps to reach at the top

    if (dp[n] == 0) {
      // if we take 1 step, we are left with 'n-1' steps;
      int take1Step = countWaysRecursive(dp, n - 1);
      // similarly, if we took 2 steps, we are left with 'n-2' steps;
      int take2Step = countWaysRecursive(dp, n - 2);
      // if we took 3 steps, we are left with 'n-3' steps;
      int take3Step = countWaysRecursive(dp, n - 3);
      dp[n] = take1Step + take2Step + take3Step;
    }

    return dp[n];
  }

  public static void main(String[] args) {
    Solution sc = new Solution();
    System.out.println(sc.countWays(3));
    System.out.println(sc.countWays(4));
    System.out.println(sc.countWays(5));
  }
}

What is the time and space complexity of the above solution? Since our memoization array dp[n+1] stores the results for all the subproblems, we can conclude that we will not have more than subproblems (where 'n' represents the total number of steps). This means that our time complexity will be . The space complexity will also be ; this space will be used to store the recursion-stack.

Bottom-up Dynamic Programming

Let's try to populate our dp[] array from the above solution, working in a bottom-up fashion. As we saw in the above code, every CountWaysRecursive(n) is the sum of the previous three counts. We can use this fact to populate our array.

Code

Here is the code for our bottom-up dynamic programming approach:

class Solution {

  public int countWays(int n) {
    if (n < 2) return 1;
    if (n == 2) return 2;

    int dp[] = new int[n + 1];
    dp[0] = 1;
    dp[1] = 1;
    dp[2] = 2;

    for (int i = 3; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];

    return dp[n];
  }

  public static void main(String[] args) {
    Solution sc = new Solution();
    System.out.println(sc.countWays(3));
    System.out.println(sc.countWays(4));
    System.out.println(sc.countWays(5));
  }
}

The above solution has time and space complexity of .

Memory optimization

We can optimize the space used in our previous solution. We don't need to store all the counts up to 'n', as we only need three previous numbers to calculate the next count. We can use this fact to further improve our solution:

class Solution {

  public int countWays(int n) {
    if (n < 2) return 1;
    if (n == 2) return 2;

    int n1 = 1, n2 = 1, n3 = 2, temp;
    for (int i = 3; i <= n; i++) {
      temp = n1 + n2 + n3;
      n1 = n2;
      n2 = n3;
      n3 = temp;
    }
    return n3;
  }

  public static void main(String[] args) {
    Solution sc = new Solution();
    System.out.println(sc.countWays(3));
    System.out.println(sc.countWays(4));
    System.out.println(sc.countWays(5));
  }
}

The above solution has a time complexity of and a constant space complexity .

Fibonacci number pattern

We can clearly see that this problem follows the Fibonacci number pattern. The only difference is that in Fibonacci numbers every number is a sum of the two preceding numbers, whereas in this problem every count is a sum of three preceding counts. Here is the recursive formula for this problem:

CountWays(n) = CountWays(n-1) + CountWays(n-2) + CountWays(n-3), for n >=3

This problem can be extended further. Instead of taking 1, 2, or 3 steps at any time, what if we can take up to 'k' steps at any time? In that case, our recursive formula will look like:

CountWays(n) = CountWays(n-1) + CountWays(n-2) + CountWays(n-3) + ... + CountWays(n-k), for n >= k

I'm working on the problem **Solution Staircase** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Explain the optimal approach to **Solution Staircase** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

I'll paste my solution to **Solution Staircase**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Give me 2 problems that use the SAME underlying pattern as **Solution Staircase**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.