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

CodePudding user response：

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, there are two edge-cases: there are no stairs at all - the output is 0, and the second is when we have only one stair then we have to take one step and the output is 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 no 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;
}

Output

1
3

CodePudding user response：

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;