Java Programming : Dynamic Programming on stairs e

问题:

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

回答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]

回答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.

回答3:

1.) map is an integer array. The notation in Java is that map[n] returns the integer value at index n.

2.) The return is an integer because map[n] returns the integer value at index n. The only time a value is saved to the array is at

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 the possible 1 , 2, and 3 combinations.

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 the complexity would be much faster than O(3^n).

回答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;
}

回答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 is 27. For the line that is commented. Can someone comment why my thought process were wrong?