Introduction to Dynamic Programming, by Daily Coding Problem

Good morning! Here's your coding interview problem for today.

This problem was asked by Amazon.

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

For example, if N is 4, then there are 5 unique ways:

• 1, 1, 1, 1
• 2, 1, 1
• 1, 2, 1
• 1, 1, 2
• 2, 2

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.

Dynamic Programming (aka DP) is by far the most loathed algorithm type for those studying algorithms and/or preparing for technical interviews. I don't like it either. I mean, I actually like it, but as I said before, it just doesn't come naturally to me, unlike recursion, queues, tries, trees, stacks, search problems, ML, which are usually more straightforward for me to grasp than DP.

I guess the reason is that, at least back in the day, we did not learn DP that well in College, or Grad School. Not sure if that's changing.

DP is a solution by construction, bottoms-up, rather than by divide-n-conquer top-down. If you want to solve a problem for "N" using DP, usually you'll want to solve for 0, then 1, then 2, all the way to N.

The general case for the problem above is the interesting one:

"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."

So let's suppose that N = 8 and X = {2, 3, 5) (the first three prime numbers). That way there are 6 combinations:

2 2 2 2
2 3 3
3 5
5 3
3 2 3
3 3 2

DP won't give you all the solutions, but it will give you the count of solutions. In this case, the way that I approached the problem was the following: for me to get to N, first I need to reach the solution for N-2, because then I can take 2 steps and get to N, OR reach the solution for N-3, because then I can take 3 steps and get to N, OR reach the solution for N-5, because then I can take 5 steps to get to N.
Hence, Solution(N) = Solution(N-2) + Solution(N-3) + Solution(N-5)

Great, that's have way through the solution. But now let's not make the mistake of recursively trying to solve this problem - if you do that you'll get into serious exponential dire straits. Instead, we'll build the solutions starting from x=0 all the way to x=N. Here we go:

If N=0, there is only one way to climb: take no steps!!! Hence, Solution(0) = 1.

Now we can go for x=1..N applying the following formula: Solution(x) = Solution(x-2) + Solution(x-3) + Solution(x-5). Now, of course, if x-k (k in X) is a negative number, well assume that there is no solution, hence Solution(y)=0 for y<0.

To do the above it only takes a simple for loop. Then you will return Solution(N). Complexity is O(N*|X|)-time and O(N)-space. We can even run for a bigger number like N=432: Solution(432) = 3477570649878420545. Massive. Here is the code on GitHub and inline, cheers, Marcelo.

GitHub: https://github.com/marcelodebarros/dailycodingproblem/blob/master/DailyCodingProblem09262018.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DailyCodingProblem
{
class DailyCodingProblem09262018
{
public long StaircaseUniqueWays(int N, int[] steps)
{
long[] stair = new long[N + 1];

stair[0] = 1;

for (int i = 1; i <= N; i++)
{
long val = 0;
for (int j = 0; j < steps.Length; j++)
if (i - steps[j] >= 0)
val += stair[i - steps[j]];
stair[i] = val;
}

return stair[N];
}
}
}