回溯 N 楼梯问题获得 0 例 Java-解网

问：

N 楼梯问题是计算到达顶部的不同方式的数量。每次您都可以爬 1 或 2 级台阶。例如，如果输入为 3，则所需输出为 3 （1+1+1,1+2,2+1）。

我正在学习 Java 中的回溯，所以我想在这个问题中实现它，尽管 DP 在这种情况下会更好。如果我很好地理解回溯，我认为这是一种实践，但显然不是。我被卡住了，因为我的算法为我提供了每种情况的输出。以下是我的代码：0

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

你能帮我弄清楚我的代码出了什么问题吗？我尝试调试它，我注意到每次它返回时，都会自动更改为，但我就是想不通为什么。cnt0

提前非常感谢！

编辑版本：

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

Java 算法递归回溯按值传递

Java 是按值传递的。这意味着你的方法中的变量没有被共享;它对你来说是独一无二的。调用时，传递它所保存的值（每次都在这里），并有自己的变量（也称为）。它修改自己的值，当该方法结束时，该值被扔进垃圾箱（当方法结束时，所有参数和所有局部变量总是被扔进垃圾箱）。cntclimbStairsclimb0climbcntcnt

您要返回：cnt

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

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

基本情况 - 表示结果已知的边缘情况（或多种情况）。对于这个问题，如果我们选择跟踪台阶数（今后我会说这不是强制性的），那么基本情况是当楼梯数等于台阶数时，即 .如果我们不跟踪步数，那么基本情况将用两个边缘情况表示：根本没有楼梯 - 不需要台阶，只有一种方法可以采取零步，所以输出是，第二个是当我们只有一个楼梯时，我们必须采取一步，输出也是。k == n11
递归大小写 - 是递归调用 made 的部分，也是主逻辑所在的部分。

在递归情况下，我们有两个可能的分支：我们可以采取 1 步或 2 步。因此，我们必须进行两个递归调用来表示这些情况。所有这些调用都可以以图形方式表示为树。为了更好地理解逻辑，您可以从在中进行的第一个方法调用开始，并跟踪每个调用的值。在条件是肉之前，每个顶点将生成两个分支。当大于或等于调用命中基本情况时。从底部到顶部，您可以计算出每个调用的返回值是多少。k < nclimbStairs()kk < nkn

另外，请注意，方法必须返回找到的路径数，而不是方法。表示这个数字的第三个参数是多余的。void

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

正如我上面所说，不需要跟踪步数。相反，我们可以在进行递归调用时减少楼梯数。这将使我们能够将所有逻辑放在一个方法中。诸如此类：

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

输出

1
3

0赞 Cary Swoveland 2/25/2022 #3

我们被赋予了有步骤。设等于所采取的两步数（）。如果采取两步走，则采取一步。Nn0 <= n <= N/2nN-2*n

当有两步时，设相等于一步和两步的组合数。这只是具有两个不同项的多项式分布中的一个系数：f(n)n

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

为了获得所需的组合总数，我们只需将相加。f(n)n = 0..N/2

对于（问题中给出的示例），组合的数量计算如下。N = 3

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

对于，组合数的计算方法如下。N = 5

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

上一个：指针在从函数 [duplicate] 返回后为 NULL

下一个：当一个对象作为另一个类的构造函数的参数传递时，它是否引用同一个对象？

回溯 N 楼梯问题获得 0 例 Java

Backtracking N stairs question getting 0 cases Java

评论

评论