Algorithms for Coding Interviews in C#/

...

/

Solution: The Staircase Problem

Solution: The Staircase Problem

Explore various approaches to solving the staircase problem in detail.

We'll cover the following...

Solution 1: Brute force

using System;
class Program
{
    /// <summary>
    /// Calculates the number of ways a stair can be climbed.
    /// </summary>
    /// <param name="n">Number of stairs.</param>
    /// <returns>Number of ways to climb a stair.</returns>
    public static int CountWays(int n)
    {
        if (n < 0)
        {
            return 0;
        }
        else if (n == 0)
        {
            return 1;
        }
        else
        {
            return CountWays(n - 1) + CountWays(n - 2) + CountWays(n - 3);
        }
    }
    // Driver code to test the above method
    public static void Main(string[] args)
    {
        Console.WriteLine("Number of ways: " + CountWays(3));
    }
}

Explanation

This solution works very similarly to the Fibonacci problem’s recursive solution. In fact, it follows the same pattern. The main idea is that if you have nn stairs, then you can hop either 1, 2, or 3 steps.

  • If you hop 1 step, then you have n−1n-1 remaining stairs.
  • If you hop 2 steps, then you have n−2n-2 remaining stairs.
  • If you hop 3 steps, then you have n−3n-3
...