Search⌘ K
AI Features
Home
Courses
Algorithms for Coding Interviews in C#

Solution: The Staircase Problem

Explore multiple dynamic programming approaches to solve the Staircase Problem, including brute force recursion, memoization to avoid redundant calculations, tabulation for building solutions iteratively, and a space-optimized technique that reduces memory usage while maintaining time efficiency.

We'll cover the following...

Solution 1: Brute force

C# 9.0
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
...