java - 一个 child 正在爬 n 步楼梯，可以跳 1 步、2 步或 3 步(每次 session 只能跳一次)

Question

我有一项学校作业，但我不知道该做什么。这是问题:

A child is climbing up a staircase with n steps, and can hop either 1 step, 2 steps, or 3 steps (only once per session) at a time. Implement a method to count how many possible ways the child can jump up the stairs

我知道如何编写具有恒定跳转次数的代码，但不知道如何使每个 session 只进行一次 3 步跳转。

我有一个必须使用的 boolean 值，但我不知道是什么。

static int climb3(int n, boolean can) {
      if (n < 0)
            return 0;
        else if (n == 0)
            return 1;
        else if(can==false)
            return climb3(n - 1,can) + climb3(n - 2,can) + climb3(n - 3,can);
}

如何在一次使用后关闭 climb 3 以不计算它？谢谢!

Answer 1

继续。你快到了:

提示:您需要一个最终的“分支:在您的”if else if ...”链中来处理 can == true 情况。

提示 2:假设 can == false 意味着您不能进行 3 步跳转，那么对于这种情况您的递归是不正确的。

---

解决方案:(未测试)

static int climb3(int n, boolean canMake3stepJump) {
    if (n < 0) {
        return 0;
    } else if (n == 0) {
        return 1;
    } else if (canMake3stepJump) {
        return climb3(n - 1, true) + climb3(n - 2, true) + 
               climb3(n - 3, false);
    } else {
        return climb3(n - 1, false) + climb3(n - 2, false);
    }
}

我建议您尝试理解在 canMake3stepJump 为 true 的情况下递归是如何工作的。写出递归调用树可能会有所帮助。