Recursion on staircase

问题:

I'm trying to understand the solution provided in a book to the following 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 book's solution is as follows, stemming from the fact that "the last move may be a single step hop from n - 1, a double step hop from step n - 2 or a triple step hop from step n - 3"

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

My confusion is:

1. Why should the program return 1 if the number of steps is zero? The way I think about it, if the number of steps is zero, then there are zero ways to traverse the staircase. Wouldn't a better solution be something like "if (n <= 0) return 0; else if (n == 1) return 1"?

2. I'm not sure I understand the rationale behind making this a static method? Google says that a static method is one that is called by the entire class, and not by an object of the class. So the book's intention seems to be something like:

.

class Staircase {
    static int n;
public:
    static int countWaysDP(int n, int[] map); }

instead of:

class Staircase {
    int n;
public:
    int countWaysDP(int n, int[] map); }

Why? What's the problem with there being multiple staircases instantiated by the class?

Thanks.

(Note: Book is Cracking the Coding Interview)

回答1:

Answer 2: A Static method means the function doesn't need any information from the object.

The function just takes an input (in the parameters), processes it and returns something. When you don't see any "this" in a function, you can set it as static.

Non-static methods usually read some properties (this-variables) and/or store values in some properties.

---

Answer 1: I converted this to javascript, just to show what happens.

http://jsbin.com/linake/1/edit?html,js,output

I guess this is the point. Recursion often works opposite to what you could expect. It often returns values in the opposite order. For 5 staircases: First it returns n=1; then n=2, ... up to n=5;
n=5 has to wait until n=4 is ready, n=4 has to wait until n=3 is ready, ...

So here is your n=0 and n<0: The first return of the function has n=1; that calls this

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

So that is

map[n] = countWaysDP(0, map) + countWaysDP(-1, map) + countWaysDP(-2, map)

There countWaysDP(0, map) returns 1; the other terms are meaningless, so they return 0. That's why there are these clauses for n==0 and n<0

notice, you can add

+ countWaysDP(n - 4, map)

if you want to see what happens when the child can also jump 4 cases

Also notice: As I said in answer 2, you see this function doesn't require any object. It just processes data and returns something. So, in your case, having this function in your class is useful because your functions are grouped (they 're not just loose functions scattered around your script), but making it static means the compiler doesn't have to carry around the memory of the object (especially the properties of the object).

I hope this makes sense. There are surely people that can give more accurate answers; I'm a bit out of my element answering this (I mostly do javascript).

回答2:

To answer your first question, it turns it is the beauty of mathematics: if there is 1 step for the staircase, there is 1 way to solve it. If there is 0 steps, there is also 1 way to solve it, which is to do nothing.

It is like, for an n-step staircase, for m times, you can either walk 1, 2, or 3 steps to finish it. So if n is 1, then m is 1, and there is 1 way. If n is 0, m is 0, and there is also 1 way -- the way of not taking any step at all.

If you write out all the ways for a 2-step staircase, it is [[1, 1], [2]], and for 1-step staircase, it is [[1]], and for 0-staircase, it is [[]], not []. The number of elements inside of the array [[]] is 1, not 0.

This will become the fibonacci series if the problem is that you can walk 1 step or 2 steps. Note that fib(0) = 1 and fib(1) = 1, and it corresponds to the same thing: when staircase is 1 step, there is 1 way to solve it. When there is 0 steps, there is 1 way to solve it, and it is by doing nothing. It turns out the number of ways to walk a 2-step staircase is fib(2) is 2 and it equals fib(1) + fib(0) = 1 + 1 = 2, and it wouldn't have worked if fib(0) were equal to 0.

回答3:

To try and answer your first question, why it returns 1 instead of 0, say you're looking at a stair with 2 steps in total, the recursive call then becomes:

countWaysDP(2 - 1, map) + countWaysDP(2 - 2, map) + countWaysDP(2 - 3, map);

The second recursive call is the one where n becomes zero, that's when we have found a successful path, because from 2 steps, there's obviously a path of taking 2 steps. Now, if you write as you suggested:

n == 1: return 1 

you would not accept taking two steps from the two stepped stair! What the statement means is that you only count the path if it ends with a single step!

回答4:

You need to think about it has a tree with 3 possible options on each node. If the size of the staircase is 4 we will have something like this:

(4)--1-->(3)--..(Choose a step and keep branching)...
  |__2-->(2)--..(Until you get size of zero)............
  |__3-->(1)--1-->(0) # <--Like this <--

At the end if you count all the leafs with size of zero you will get all the possible ways.

So you can think it like this, what if you take a step and then consider update the size of the stair like this size-step, where your steps can be (1,2,3)

Doing that you can code something like this:

choices = (1, 2, 3)
counter = 0

def test(size):
    global counter

    if size == 0:
        counter += 1

    for choice in choices:
        if size - choice >= 0:
            test(size - choice)

    return counter