Dynamic Programming: Child running up a staircase

Question

I'm starting to practice Dynamic Programming and I just can't wrap my head around this question:

Question:

A child is running up a staircase with n steps and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs.

The solution from the cracking the coding interview book is like this:

"If we thought about all the paths to the nth step, we could just build them off the paths to the three previous steps. We can get up to the nth stop by any of the following:

Going to the (n-1) step and hopping 1 step
Going to the (n-2) step and hopping 2 steps
Going to the (n-3) step and hopping 3 steps"

Therefor to find the solution you just add the number of these path together !

That's what loses me ! Why isn't the answer like this: add number of those paths then add 3 ? Since if you are on step n-1 or n-2 or n-3, there are 3 ways to get the nth step? I understand that if you write down the answers for the first 4 bases cases (assuming that n=0 returns 1) You can see the fibonacci-like pattern. But you may not also see it so it's difficult.

And then they came up with this code:

public static int countWaysDP(int n, int[] map) {
if (n < 0) 
    return 0;
else if (n == 0)
    return 1;
else if (map[n] > -1)
    return map[n];
else {
    map[n] = countWaysDP(n - 1, map) + countWaysDP(n - 2, map) + countWaysDP(n - 3, map);
    return map[n]; }

}

So my second question. How does it return 1 when n == 0. Even if I accept that fact, I still can't figure out a way to solve it if I return 0 when n == 1.

Hope this makes sense.

Thank you

score 0 · Answer 1 · answered Aug 26 '19 at 15:53

Here is how I wrapped my head around this-

From the book -

On the very last hop, up to the nth step, the child could have done either a single, double, or triple step hop. That is, the last move might have been a single step hop from step n-1, a double step hop from step n-2, or a triple step hop from n-3. The total number of ways of reaching the last step is therefore the sum of the number of ways of reaching each of the last three steps

You are correctly contemplating -

Why isn't the answer like this: add number of those paths then add 3 ? Since if you are on step n-1 or n-2 or n-3, there are 3 ways to get the nth step?

The problem with such a base case is that it will be applicable only if n >= 3. You clearly will not add 3 if there are only 2 steps.

Let's break down the individual cases and understand what exactly is the base case here.

n=0

There are no stairs to climb.

Total number of ways = 0

n=1

Total number of ways = 1StepHop from (n-1)
Number of ways to do 1StepHop from Step 0(n-1) = 1

Total number of ways = 1

n=2

Total number of ways = 2StepHop from (n-2) + 1StepHop from (n-1)
Number of ways to do 2StepHop to reach Step 2 from Step 0(n-2) = 1
Number of ways to do 1StepHop to reach Step 2 from Step 1(n-1) = 1 (Previous answer for n=1) 

Total number of ways = 1 + 1 = 2

n=3

Total number of ways = 3StepHop from (n-3) + 2StepHop from (n-2) + 1StepHop from (n-1)
Number of ways to do 3StepHop to reach Step 3 from Step 0(n-3) = 1
Number of ways to do 2StepHop to reach Step 3 from Step 1(n-2) = 2 (From previous answer for n = 2)
Number of ways to do 1StepHop to reach Step 3 from Step 2 = 1 (From previous answer for n=1) 

Total number of ways = 1 + 2 + 1 = 4

Observation - As you can see from above, we are correctly accounting for the last step in each case. Adding one for each of -> 1StepHop from n-1, 2StepHop from n-2 and 3StepHop from n-3.

Now looking at the code, the case where we return 1 if n==0 is a bit counter-intuitive since we already saw that the answer should be 0 if n==0. -

public static int countWaysDP(int n, int[] map) {
if (n < 0) 
    return 0;
else if (n == 0) 
    return 1;  <------------- this case is counter-intuitive
else if (map[n] > -1)
    return map[n];
else {
    map[n] = countWaysDP(n - 1, map) + countWaysDP(n - 2, map) + countWaysDP(n - 3, map);
    return map[n];
}

From the observation, you can see that this counter intuitive case of n==0 is actually the one which is accounting for the final step - 1StepHop from n-1, 2StepHop from n-2 and 3StepHop from n-3.

So hitting n==0 case makes sense only during recursion - which will happen only when the initial value of n is greater than 0.

A more complete solution to this problem may have a driver method which handles that case outside of the core recursive algorithm -

int countWays(int n) {
    if (n <= 0 ) return 0;
    int[] map = new int[n+1];
    for(int i = 0; i<n+1; i++){
        map[i] = -1;
    }
    return countWaysDP(n, map);
}

Hope this is helpful.

crispengari · Answer 2 · 2020-05-29T13:11:00.233

You can find the solution on https://github.com/CrispenGari/Triple-Step-Algorithim/blob/master/main.cpp .

int count_Ways(int n){
   if(n<0){
      return 0;
   }else if(n==0){
      return 1;
   }else{
      return count_Ways(n-1) +count_Ways(n-2) + count_Ways(n-3);
  }
}
int main(){
   cout<<"Enter number of stairs: ";
   int n;
   cin>>n;
   cout<<"There are "<< count_Ways(n)<<"  possible ways the child can run up 
   thestairs."<<endl;
   return 0;
}

Dynamic Programming: Child running up a staircase

2 Answers2