Java Programming: Dynamic Ladder Programming

Question

A person climbs the stairs with n steps and can go either 1 step, or 2 steps, or 3 steps at a time. Now write a program to calculate the number of possible ways that a child can control the stairs.

Code 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. Can anyone explain

• why and how does she use the feature map here? Is the map here an array on the right?

• I don’t see any line to save the input to the map array, but how would it return something?

• Does anyone have an idea for a C ++ or C version of this code? It is hard to understand this code. Perhaps not because of the JAVA grammar, but in the implicit structure of dynamic programming.

• What will be the time complexity of this algorithm? Should it be less than O (3 ^ n)?

I would be very grateful.

Thanks guys

Answer 1

Ok, here is what the code does.

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

If there are not enough steps left, then do not count. For example, if two steps remain, but the user tries to take three steps, then this is not considered a possible combination.

else if (n==0) return 1;

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

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

This is part of dynamic programming. Suppose all values ​​in the array have a value of -1. So, if the number is greater than -1, it has already been decided for, so return the total number of combinations from step 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 that the user can receive if he takes 1 step + the number of possible combinations that the user can receive if he takes 2 steps + the number of possible combinations that the user can get if he takes three steps.

For example, suppose there are 5 steps

A simple run would look like this:

 //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] 

Answer 2

why and how does she use the feature map here?

The book introduces a dynamic programming method called memoization . It is used to avoid recalculating the same number: if the element is not -1 , then it was calculated again, and recalculation would mean wasting a lot of processor cycles. DP calculates the value once, and then returns it every time a value is required.

is the array displayed here on the right?

That's right, map has an array type.

I don’t see any line to save the input to the map array, but how would it return something?

This will be the assignment on the third line from below:

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

Does anyone have an idea for a C ++ or C version of this code? It is hard to understand this code. Perhaps not because of the JAVA grammar, but in the implicit structure of dynamic programming.

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

What will be the time complexity of this algorithm? Should it be less than O (3 ^ n)?

Absolutely! Each element is calculated exactly once, and each element depreciates O(1) for calculation, so the overall complexity of this code is O(N) . This can be inconsistent, as you watch the chain of recursive calls to calculate countDP(K) accept recursive calls O(K) . However, each call completes the calculation of the K map elements (note how map is a one-way street: after you set a non-negative value to the cell, it will remain non-negative forever, so recalculating the same value using any other path A call will result in the same O(1) .

Answer 3

1.) map - an integer array. A designation in Java means that map [n] returns an integer value at index n.

2.) Return is an integer because map [n] returns an integer value in index n. The only time a value is stored in an array is in

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

This is a recursive call to find the sum of steps by counting all possible combinations of 1, 2, and 3.

3).

 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]; } } 

4.) Yes, complexity will be much faster than O (3 ^ n).

Answer 4

JavaScript solution: (iterative)

 function countPossibleWaysIterative(n) { if (n < 0){ return -1; // check for negative, also might want to check if n is an integer } if (n === 0) { return 0; // for case with 0 stairs } else if (n === 1) { return 1; // for case with 1 stairs } else if (n === 2) { return 2; // for case with 2 stairs } else { var prev_prev = 1; var prev = 2; var res = 4; // for case with 3 stairs while (n > 3) { // all other cases var tmp = prev_prev + prev + res; prev_prev = prev; prev = res; res = tmp; n--; } } return res; } 

Answer 5

 /** * Created by mona on 3/3/16. */ import java.util.Hashtable; public class StairCount { /* A man is running up a staircase with n steps, and can go either 1 steps, 2 steps, or 3 steps at a time. count how many possible ways the child can run the stairs. */ static Hashtable<Integer, Long> ht=new Hashtable<>(); public static long stairs(int n){ if (!ht.containsKey(1)){ ht.put(1, (long) 1); } if (!ht.containsKey(2)){ ht.put(2, (long) 2); } if (!ht.containsKey(3)){ ht.put(3, (long) 4); } /* if (!ht.containsKey(n)){ ht.put(n, stairs(n-1)+ht.get(1)+stairs(n-2)+ht.get(2)+stairs(n-3)+ht.get(3)); } */ if (!ht.containsKey(n)){ ht.put(n, stairs(n-1)+stairs(n-2)+stairs(n-3)); } return ht.get(n); } public static void main(String[] args){ System.out.println(stairs(4)); } } 

// the answer for 4 is 14, and for 5 it is 27. For the line that is commented out. Can someone comment on why my thought process was wrong?