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

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

谢谢,

Answer 1

首先，你需要理解递归公式，以及我们是如何从中推导出迭代公式的。

递归公式为:

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

(f(n-1)为一步，f(n-2)为两步，总数是使用这些选项之一的方法的数量-因此是求和)。

如果你仔细看——这也是一个著名的数列——斐波那契数列，解决方案是简单地计算每个数字，而不是一次又一次地重新计算递归，从而产生更有效的解决方案。

Answer 2

用DP爬楼梯

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

Answer 3

在动作中写下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));