解释这个动态规划爬楼梯代码

Question

问题是：

“你正在爬楼梯，每次可以爬1步或2步。这个楼梯有n个台阶。你能以多少种不同的方式爬完整个楼梯？”

以下是解决此问题的代码解决方案，但我无法理解它。有人可以解释一下吗？

int stairs(int n) {
  if (n == 0) return 0;
  int a = 1;
  int b = 1;
  for (int i = 1; i < n; i++) {
    int c = a;
    a = b;
    b += c;
  }
  return b;
 }

谢谢。

- Deepesh M

Answer 1

首先，您需要了解递归公式以及我们如何从中导出迭代公式。

递归公式为：

f(n) = f(n-1) + f(n-2)
f(0) = f(1) = 1

(一个步骤f(n-1)，两个步骤f(n-2)，总数是使用其中一种选项的方式数量-因此求和）。

如果你仔细看，这也是一个众所周知的序列——斐波那契数列，解决方案就是从下往上计算每个数字，而不是一遍又一遍地重新计算递归，从而得到更有效的解决方案。

- amit

---

斐波那契数列中，f(0) 不是等于 0 吗？ - Amir Afghani

代码中让我困惑的部分是a和b。它们代表什么，为什么都是1？ - Deepesh M

a 代表 f(n-1)，b 代表 f(n-2)。 - Amir Afghani

但它并不打印所有可能的组合，它只计算它们。 - bsobaid

@bsobaid 这就是问题所在。 - amit

Answer 2

在写下到达特定楼层的1步和2步可能选项时，有人发现组合数量恰好是斐波那契数列中的一个数字。这就是答案。选项数量（2个选项：1步和2步）与为获得斐波那契数列中下一个数字而相加的数字数量之间存在关系：两个数字。因此，如果您尝试使用3个选项（1步、2步、3步）解决攀登楼梯问题，则结果等同于调整斐波那契数列但要求相加3个数字，该序列将为0、1、1、2、4、7、13、24。我不知道这个序列是否有名称，但如果您检查，结果是正确的。

回到使用1-2步攀登楼梯的问题，对于下一个代码，我使用一个数组作为堆栈，而不是使用3个变量或数组（其他可以在网络上找到的解决方案）。我弹出前两个数字，计算出当前数列中的当前数字，然后推入最近的前一个数字，再推入当前数字。这两个数字将成为while循环下一个周期中的前一个数字。

 /**
 * Using Fibonacci and a stack.
 * @param {number} n
 * @return {number}
 */
const climbingStairs = (n) => {
    if (n === 0) return 0;
    if (n === 1) return 1;
    if (n === 2) return 2;

    let stack = [];
    stack.push(1);
    stack.push(2);
    let current_steps = 3;
    let current_combinations = 0;
    while (current_steps <= n) {
        let previous = stack.pop();
        let previous2 = stack.pop();
        current_combinations = previous + previous2;
        stack.push(previous);
        stack.push(current_combinations);
        current_steps++
    }
    return current_combinations
}

console.log(climbingStairs(5));

- Marcelo Fernández

---

欢迎来到 Stack Overflow。当代码配合解释时，它会更有帮助。Stack Overflow 的目的是为了学习，而不是提供盲目复制粘贴的片段。请编辑您的问题并解释它如何回答特定的问题。请参见[答案]。 - Chris

Answer 3

使用动态规划爬楼梯

class Solution {
   public:
     int climbStairs(int n) {
    int dp[n+1];

    if (n <= 1)
        return 1;

    if (n ==2)
        return 2;

    dp[0] = 1;
    dp[1] = 1;
    dp[2] = 2;

    for (int i = 3; i <=n; i++){
        dp[i] = dp[i-1]+dp[i-2];
    }

    return dp[n];
   }};

- Purva