回溯 N 阶梯问题得到 0 个案例 Java
Backtracking N stairs question getting 0 cases 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;
}
}
}
你能帮我弄清楚我的代码有什么问题吗？我试着调试了一下，发现每次returns，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;
}
}
Java 是 pass-by-value。这意味着您的 climbStairs 方法中的 cnt 变量未共享；它对你来说是独一无二的。当您调用 climb 时，您传递它持有的值（这里每次都是 0），并且 climb 有自己的变量（也称为 cnt）。它修改自己的 cnt 值，该值在该方法结束时被扔进垃圾箱（当方法结束时，所有参数和所有局部变量总是被扔进垃圾箱）。
您想return cnt:
// In climbStairs:
return climb(cnt, k, n);
// In climb, at the end:
return cnt;
每个递归实现都包含两部分:
- 基本情况 - 代表 edge-case 结果已知的一种（或多种）情况。对于这个问题，如果我们选择跟踪 steps 的数量（接下来我会说这不是强制性的）那么 base case 是当阶梯数等于阶梯数时，即
k == n。如果我们不跟踪 steps 的数量，那么 base case 将用 two edge-case 表示s：根本 没有楼梯 - 不需要 步 并且只有一种方法可以采取零步，所以输出是1，第二个是当我们只有一个楼梯时，我们必须走一个step，输出也是1.
- recursive case - 是递归调用和主要逻辑所在的部分。
对于每个k < n，在递归情况中我们有两个可能的分支：我们可以采取1步或2步。因此我们必须进行 两次递归调用 来表示这些情况。所有这些调用都可以图形方式表示为一棵树。为了更好地理解逻辑，您可以从 climbStairs() 中的第一个树开始绘制 method-calls 的 树并跟踪 [=18= 的值吗？ ] 每次通话。在条件 k < n 是肉之前，每个 vertex 将生成两个分支。当 k 大于或等于 n 时，调用符合 基本情况 。从底部到顶部，您可以找出每个调用的 return 值。
此外，请注意，您的方法必须 return 而不是 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
我们知道有 N 个步骤。让 n 等于 two-steps 的数量 (0 <= n <= N/2)。如果 n two-steps 被占用 N-2*n one-steps 被占用。
当有ntwo-steps时，令f(n)等于one-steps和two-steps的组合数。这只是 multinomial distribution 中的一个系数，有两个不同的项目：
m = N-2*n
f(n) = (n+m)!/(n!*m!)
为了获得所需的总组合数，我们只需对 n = 0..N/2 求和 f(n)。
对于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
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;
}
}
}
你能帮我弄清楚我的代码有什么问题吗？我试着调试了一下，发现每次returns，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;
}
}
Java 是 pass-by-value。这意味着您的 climbStairs 方法中的 cnt 变量未共享；它对你来说是独一无二的。当您调用 climb 时，您传递它持有的值（这里每次都是 0），并且 climb 有自己的变量（也称为 cnt）。它修改自己的 cnt 值，该值在该方法结束时被扔进垃圾箱（当方法结束时，所有参数和所有局部变量总是被扔进垃圾箱）。
您想return cnt:
// In climbStairs:
return climb(cnt, k, n);
// In climb, at the end:
return cnt;
每个递归实现都包含两部分:
- 基本情况 - 代表 edge-case 结果已知的一种（或多种）情况。对于这个问题，如果我们选择跟踪 steps 的数量（接下来我会说这不是强制性的）那么 base case 是当阶梯数等于阶梯数时，即
k == n。如果我们不跟踪 steps 的数量，那么 base case 将用 two edge-case 表示s：根本 没有楼梯 - 不需要 步 并且只有一种方法可以采取零步，所以输出是1，第二个是当我们只有一个楼梯时，我们必须走一个step，输出也是1. - recursive case - 是递归调用和主要逻辑所在的部分。
对于每个k < n，在递归情况中我们有两个可能的分支：我们可以采取1步或2步。因此我们必须进行 两次递归调用 来表示这些情况。所有这些调用都可以图形方式表示为一棵树。为了更好地理解逻辑，您可以从 climbStairs() 中的第一个树开始绘制 method-calls 的 树并跟踪 [=18= 的值吗？ ] 每次通话。在条件 k < n 是肉之前，每个 vertex 将生成两个分支。当 k 大于或等于 n 时，调用符合 基本情况 。从底部到顶部，您可以找出每个调用的 return 值。
此外，请注意，您的方法必须 return 而不是 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
我们知道有 N 个步骤。让 n 等于 two-steps 的数量 (0 <= n <= N/2)。如果 n two-steps 被占用 N-2*n one-steps 被占用。
当有ntwo-steps时，令f(n)等于one-steps和two-steps的组合数。这只是 multinomial distribution 中的一个系数，有两个不同的项目：
m = N-2*n
f(n) = (n+m)!/(n!*m!)
为了获得所需的总组合数，我们只需对 n = 0..N/2 求和 f(n)。
对于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