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

Question

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

你能帮我找出我的代码有什么问题吗？我尝试调试它，我注意到每次返回时，cnt都会自动更改为0，但我就是不明白为什么。

提前非常感谢！

编辑版本：

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

Answer 1

每个递归实现都由两部分组成：

• 基本情况 - 表示结果已知的边缘情况的情况（或情况）。对于这个问题，如果我们选择跟踪步数（展望未来，我想说这不是强制性的），那么基本情况就是当步数>stairs等于步数，即k == n。如果我们不跟踪步数，那么基本情况将用两个边缘情况表示：有根本没有楼梯 - 不需要步骤，并且只有一种方法可以走零步，所以输出是1，第二种是当我们只有一个楼梯那么我们必须走一个步骤，输出也是1。
• 递归情况 - 是递归调用和主要逻辑所在的部分。

对于每个k <<，在递归情况中，我们有两个可能的分支。 n：我们可以采取1步或2步。因此，我们必须进行两次递归调用来代表这些情况。所有这些调用都可以以图形方式表示为树。为了更好地理解逻辑，您可以从 climbStairs() 内创建的第一个方法调用树开始绘制这个方法调用树，并跟踪 k 的值 每次调用。直到条件k < n 是肉，每个顶点会产生两个分支。当k大于或等于n时，调用将达到基本情况。从下到上，您可以计算出每次调用的返回值是什么。

另请注意，您的方法必须返回找到的路径数，而不是 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

Answer 2

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

您想要返回 cnt：

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

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

Answer 3

我们已知有 N 个步骤。令 n 等于所采取的两步数 (0 <= n <= N/2)。如果采取n两步，则采取N-2*n一步。

当有n个两步时，令f(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