Java Programming : Dynamic Programming on stairs example

Question

A man is running up a staircase with n steps, and can go either 1 steps, 2 steps, or 3 steps at a time. Now write a program to count how many possible ways the child can run the stairs.

The code given is like below

public static int countDP(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] = countDP(n-1, map) + countDP(n-2, map) + countDP(n-3, map);
    return map[n]; }
 }

I know C and C++, not JAVA. This is from the Cracking the Coding interview book. Could anybody can explain

1. why and how she employs the function map here? map here is array right?

2. I do not see any line to save an input to the map array but how would it return something?

3. Anybody has an idea of C++ or C version of this code? It is hard to understand this code. Maybe not because of the JAVA grammar, but the implicit structure of dynamic programming.

4. What would be the time complexity of this algorithm? It should be smaller than O(3^n) ?

I would greatly appreciate it.

Thanks, guys

Solution 1

Okay, here is what the code does.

 `if (n<0)`
    `return 0;`

If there aren't enough steps remaining, then don't count it. For instance, if there are two steps remaining, but the user is trying to take three steps, then it does not count as a possible combination.

else if (n==0) return 1;

If the number of steps remaining matches the number of available steps the user is trying to take, it is a possible combination. So, return a 1 because this is a possible combination and should be added to the total number of valid combinations.

else if (map[n]>-1) return map[n];

Here is the dynamic programming part. Assume that the all the values in the array had a value of -1. So, if the number is greater than -1, it has already been solved for, so return the total number of combinations from step number n instead of resolving it.

`map[n] = countDP(n-1, map) + countDP(n-2, map) + countDP(n-3, map);`

return map[n]; }

Finally, this part solves the code. The number of possible combinations is equal to the number of possible combinations the user can get if he takes 1 step + the number of possible combinations the user can get if he takes 2 steps + the number of possible combinations the user can get if he takes three steps.

An example, suppose there are 5 steps

A simple run would look like:

//The number of solutions from the fifth step

countDp(5) = countDp(4)+countDp(3)+countDp(2);

//Number of solutions from the fourth step

countDP(4) = countDp(3)+countDp(2)+countDp(1);

//Number of solutions from the third step

countDp(3) = countDp(2)+countDp(1)+countDp(0);
//Number of solutions from the second step
countDp(2) = countDp(1)+countDp(0)+countDp(-1);
//Number of solutions from the first step
countDp(1) = countDp(0) + countDp(-1)+countDp(-2);
//Finally, base case
countDp(0) = 1;

countDp(-1)= 0;
countDp(-2)= 0;
countDp(1) = 1+0+0 = 1;
countDp(2) = 1+1+0 = 2;  //Dynamic programming: did not have to resolve for countDp(1), instead looked up the value in map[1]
countDp(3) = 2+1+1 = 4;  //Dynamic programming, did not have to solve for countDp(1), countDp(2), instead looked up value in map[1] and map[2]
countDp(4) = 4+2+1=7 //Dynamic programming, did not have to solve for CountDp(3),CountDp(2), CountDp(1), just looked them up in map[3],map[2],map[1]
countDp(5)=  2+4+7=13 //Dynamic programming, just used map[4]+map[3]+map[2]

Solution 2

why and how she employs the function map here?

The book shows a dynamic programming technique called memoization. It is used to avoid calculating the same number again: if the element is not -1, then it has been computed again, and re-calculating it would mean wasting lots of CPU cycles. DP computes the value once, and then returns it every time the value is needed.

map here is array right?

Correct, map is of an array type.

I do not see any line to save an input to the map array but how would it return something?

That would be the assignment on the third line from the bottom:

map[n] = countDP(n-1, map) + countDP(n-2, map) + countDP(n-3, map);

Anybody has an idea of C++ or C version of this code? It is hard to understand this code. Maybe not because of the JAVA grammar, but the implicit structure of dynamic programming.

Right, DP and memoization take some time to get used to. Run through this algorithm once with paper and pencil for a small number, say, 10. This will show you how the optimal substructure of the answer helps this algorithm come up with the answer so fast.

What would be the time complexity of this algorithm? It should be smaller than O(3^n) ?

Absolutely! Each item is computed exactly once, and each item takes amortized O(1) to compute, so the overall complexity of this code is O(N). This may be counterintuitive, as you observe how the chain of recursive invocations to compute countDP(K) takes an O(K) recursive invocations. However, each invocation finishes the computation of K items of the map (note how map is a one-way street: once you set a non-negative value into a cell, it's going to stay non-negative forever, so re-computing the same value through any other invocation path would take the same O(1) time.