algorithm - Java Programming : Dynamic Programming on stairs example -

a man running staircase n steps, , can go either 1 steps, 2 steps, or 3 steps @ time. write program count how many possible ways child can run stairs.

the code given 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 , c++, not java. cracking coding interview book. can explain

1. why , how employs function map here? map here array right?

2. i not see line save input map array how return something?

3. anybody has idea of c++ or c version of code? hard understand code. maybe not because of java grammar, implicit structure of dynamic programming.

4. what time complexity of algorithm? should smaller o(3^n) ?

i appreciate it.

thanks, guys

okay, here code does.

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

if there aren't enough steps remaining, don't count it. instance, if there 2 steps remaining, user trying take 3 steps, not count possible combination.

else if (n==0) return 1;

if number of steps remaining matches number of available steps user trying take, possible combination. so, return 1 because possible combination , should added total number of valid combinations.

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

here dynamic programming part. assume values in array had value of -1. so, if number greater -1, has been solved for, return total number of combinations 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, part solves code. number of possible combinations equal number of possible combinations user can if takes 1 step + number of possible combinations user can if takes 2 steps + number of possible combinations user can if takes 3 steps.

an example, suppose there 5 steps

a simple run like:

//the number of solutions fifth step  countdp(5) = countdp(4)+countdp(3)+countdp(2);  //number of solutions fourth step  countdp(4) = countdp(3)+countdp(2)+countdp(1);  //number of solutions third step  countdp(3) = countdp(2)+countdp(1)+countdp(0); //number of solutions second step countdp(2) = countdp(1)+countdp(0)+countdp(-1); //number of solutions 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 resolve countdp(1), instead looked value in map[1] countdp(3) = 2+1+1 = 4;  //dynamic programming, did not have solve countdp(1), countdp(2), instead looked value in map[1] , map[2] countdp(4) = 4+2+1=7 //dynamic programming, did not have solve countdp(3),countdp(2), countdp(1), looked them in map[3],map[2],map[1] countdp(5)=  2+4+7=13 //dynamic programming, used map[4]+map[3]+map[2]