Count Combinations Of Steps On A Staircase With N Steps – Dynamic Programming

THE PROBLEM STATEMENT

There’s a staircase with N steps, and you can climb 1 or 2 steps at a time. Given N, write a function that returns count of unique ways you can climb the staircase. The order of the steps matters.

What if, instead of being able to climb 1 or 2 steps at a time, you could climb any number from a set of positive integers X? For example, if X = {1, 3, 5}, you could climb 1, 3, or 5 steps at a time. Generalize your function to take in X.

Example 1

Example 2

Example 3

Example 4

SOLUTION?

In the previous post “All Possible Combinations Of Steps On A Staircase With N Steps” we wrote a method that returned all possible combinations. Through the same code we could find out the count of combinations as well. But it was not an optimized solution for this problem since we only want to find out the count of all possible combinations.

One way to optimize recursion is using memorization/cache to return data so you don’t have to traverse the same tree again.

How ever using dynamic programming we can make it more optimized and faster.

Dynamic Programming

Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. In both contexts it refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner. While some decision problems cannot be taken apart this way, decisions that span several points in time do often break apart recursively. Likewise, in computer science, if a problem can be solved optimally by breaking it into sub-problems and then recursively finding the optimal solutions to the sub-problems, then it is said to have optimal substructure.

https://en.wikipedia.org/wiki/Dynamic_programming

As we can see this problem can be broken into subproblems, and it contains the optimal substructure property i.e. its optimal solution can be constructed efficiently from optimal solutions of its subproblems, we can use dynamic programming to solve this problem.

One can reach i^th step in one of the two ways:

1. Taking a single step from (i-1)^th step.
2. Taking a step of 2 from (i-2)^th step.

So, the total number of ways to reach i^th is equal to sum of ways of reaching (i-1)^th step and ways of reaching (i-2)^th step.

Let dp[i] denotes the number of ways to reach on i^th step:

dp[i] = dp[i-1] + dp[i-2]

Visual example is following:

Like wise if we have possible steps 1, 2 and 4. One can reach i^th step in one of the three possible ways:

1. Taking a single step from (i-1)^th step.
2. Taking a step of 2 from (i-2)^th step.
3. Taking a step of 4 from (i-4)^th step.

So, the total number of ways to reach i^th is equal to sum of ways of reaching (i-1)^th step, ways of reaching (i-2)^th step and ways of reaching (i-4)^th step .

Let dp[i] denotes the number of ways to reach on i^th step:

dp[i] = dp[i-1] + dp[i-2] + dp[i-4]

Visual example is following:

Lets get started then. The method I have created is following:

public static long GetTotalCombinationsDP(int staircaseSteps, int[] possibleSteps)
{
	Array.Sort(possibleSteps); // sort array
	long totalCombinations = 0;
	long[] stepCombinationTrack = new long[staircaseSteps + 1];
	// first index of array is always 0 since its representing stair with 0 steps
	stepCombinationTrack[0] = 0;

	for (int i = 1; i < stepCombinationTrack.Length; i++)
	{
		long total = 0;
		// is stair step is equal to possible step than add by 1 since possible step itself is a combination.
		if (possibleSteps.Contains(i)) total += 1;

		foreach(int possibleStep in possibleSteps)
		{
			// if possible step is less than current step number of stair
			if (i-possibleStep > 0)
			{
				total += stepCombinationTrack[i - possibleStep];
			}
		}

		stepCombinationTrack[i] = total;
	}

	totalCombinations = stepCombinationTrack[staircaseSteps];
	return totalCombinations;
}

Lets try this code now

public static void Main(string[] args)
{
	int staircaseSteps = 5;
	int[] possibleSteps = new int[] { 1, 3, 5 };

	long combDP = GetTotalCombinationsDP(staircaseSteps, possibleSteps);

	Console.WriteLine($"Combination Length: {combDP}");
	Console.ReadKey();
}

That’s it! I am looking forward to hearing from you guys in comment section below.

Thanks for stopping by! Happy coding!