Backtracking N stairs question getting 0 cases Java

user_16974852 0
Viewed 82

N Stairs question is to compute the number of distinct ways to reach the top. Each time you can either climb 1 or 2 steps. For example, if the input is 3, the desired output is 3 (1+1+1,1+2,2+1).

I am learning backtracking in Java, so I want to implement it in this question, although DP would work better in such a case. I view it as a practice if I understand backtracking well, but apparently not. I got stuck because my algorithm gives me a 0 output for every case. Below is my code:

    public int climbStairs(int n) {
        int cnt=0,k=0;
        climb(cnt,k,n);
        return cnt;
    }
    public void climb(int cnt, int k, int n){
        if(k==n){
            cnt++;
            return; 
        }
        for(int i=1;i<3;++i){
            if(k<n){
                k+=i;
                climb(cnt,k,n);
                k-=i;
            }
        }
    }

Could you help me figure out what's wrong with my code? I tried debugging it, and I noticed every time it returns, cnt will automatically change to 0, but I just can't figure out why.

Thank you so much in advance!

Edited version:

public class ClimbStairs {
    public static void main(String[] args) {
        System.out.println(climbStairs(3));
    }
    public static int climbStairs(int n) {
        int cnt=0,k=0;
        return climb(cnt, k, n);
    }
    public static int climb(int cnt, int k, int n){
        if(k==n){
            cnt++;
        }
        for(int i=1;i<3;++i){
            if(k<n){
                k+=i;
                climb(cnt,k,n);
                k-=i;
            }
        }
        return cnt;
    }
}
backtracking pass-by-value recursion algorithm java
3 Answers

Every recursive implementation consists of two parts:

  • base case - a situation (or situations) that represent the edge-case for which the result is already known. For this problem, if we choose to track the number of steps (going forward I'd say that it's not mandatory) then the base case is when the number of stairs is equal to the number of steps, i.e. k == n. And if we don't track the number of steps then the base case will be represented with two edge-cases: there are no stairs at all - no steps required and there's only one way to take zero steps, so the output is 1, and the second is when we have only one stair then we have to take one step and the output is also 1.
  • recursive case - is the part where recursive calls a made and where main logic resides.

We have two possible branches in the recursive case for every k < n: we can either take 1 step or 2 steps. And therefore we have to make two recursive calls that represent these situations. All these calls can be represented graphically as a tree. To understand the logic better can you drow this tree of method-calls starting from the first one that is made inside the climbStairs() and track the value of k for each call. Until the condition k < n is meat each vertex will spawn two branches. When k is greater or equal to n the call hits the base case. And starting from the bottom to the top you can figure out what are the return values for each call.

Also, note that instead of being void your method must return the number of paths that are found. And the third parameter that represents this number is redundant.

public static void main(String[] args) {
    System.out.println(climbStairs(1));
    System.out.println(climbStairs(3));
}

public static int climbStairs(int n) {
    if (n < 0) { // cut off the incorrect input
        return 0;
    }
    return climb(n, 0);
}

public static int climb(int n, int k){
    if (k > n) { // an invalid situation
        return 0;
    }
    if (k == n) { // a path was found
        return 1;
    }
    // there are two alternative branches for every k < n
    int count = 0;
    count += climb(n, k + 1); // move one step forward
    count += climb(n, k + 2); // move two steps forward
    return count;
}

As I said above tracking the number of steps isn't required. Instead, we can reduce the number of stairs while making recursive calls. And that will allow us to place all logic in a single method. Like that:

public static int climbStairs(int n) {
    if (n < 0) { // cut off the incorrect input
        return 0;
    }
    if (n == 0) { // a base case when we have NO stairs - we have to take zero steps (there's only ONE way to do that)
        return 1;
    }
    if (n == 1) { // a base case when we have only one stair - we have to take one step (there's only ONE way to do that)
        return 1;
    }
    // there are two alternative branches for every n > 1
    int count = 0;
    count += climbStairs(n - 1); // move one step forward
    count += climbStairs(n - 2); // move two steps forward
    return count;
}

Output

1
3
user_179499450

Java is pass-by-value. That means your that your cnt variable in your climbStairs method is not shared; it is unique to you. When you invoke climb, you pass the value it holds (0 every time here), and climb has its own variable (also called cnt). It modifies its own cnt value which is tossed in the garbage when that method ends (all parameters and all local variables are always tossed in the garbage when a method ends).

You want to return cnt:

// In climbStairs:
return climb(cnt, k, n);

// In climb, at the end:
return cnt;
user_7686440

We are given that there are N steps. Let n equal the number of two-steps taken (0 <= n <= N/2). If n two-steps are taken N-2*n one-steps are taken.

Let f(n) equal the number of combinations of one-steps and two-steps when there are n two-steps. This is merely a coefficient in a multinomial distribution having two distinct items:

m = N-2*n
f(n) = (n+m)!/(n!*m!)

To obtain the desired total number of combinations we simply sum f(n) over n = 0..N/2.

For N = 3 (the example given in the question), the number of combinations is computed as follows.

n = 0
m = N-2*n = 3
f(n) = (n+m)!/(n!*m!) = 3!/(0!*3!) = 1    # 111

n = 1
m = N-2*n = 1
f(n) = (n+m)!/(n!*m!) = 2!/(1!*1!) = 2    # 12 and 21

f(0) + f(1) = 3

For N = 5, the number of combinations is computed as follows.

n = 0
m = N-2*n = 5
f(n) = (n+m)!/(n!*m!) = 5!/(0!*5!) = 1    # 11111

n = 1
m = N-2*n = 3
f(n) = (n+m)!/(n!*m!) = 4!/(1!*3!) = 4    # 2111 1211 1121 1112

n = 2
m = N-2*n = 1
f(n) = (n+m)!/(n!*m!) = 3!/(2!*1!) = 3    # 212 221 122

f(0) + f(1) + f(2) = 8
user_2569700
Related