algorithm - 解释这个动态规划爬n-stair代码

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

In the act of write down the possible options of 1 step, 2 steps to reach a determined floor; For me, somebody saw that the number of combinations was exactly a number into the Fibonacci series. Then, this is the answer. There is a relation between the amount of options (2 options: 1 step, and 2 steps) and the amount of numbers summed to obtain the next number in the Fibonacci series: two numbers. Then if you try to solve a climbing stairs with for example 3 options (1 step, 2 steps, 3 steps) then the result is equivalent to adapt the Fibonacci series but summing 3 numbers, the series will be 0, 1, 1, 2, 4, 7, 13, 24. I don't know if this series has a name but if you check, the result is correct.

Going back to the climbing stairs with 1-2 steps, for the next code, instead of using 3 variables or an array (other solutions that you can find on the web), I'm using an array as a stack. I pop the two previous numbers, calculate the current number in the series, then push the most recent of the previous numbers and then push the current number. These two numbers will be the previous numbers in the next cycle of the while loop.

 /**
 * 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));