algorithm - 解释这个动态规划爬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)为两步，总数为使用一种的方式数这些选项的总和)。

如果你仔细看 - 这也是一个众所周知的系列 - fibonacci numbers ，解决方案是简单地计算每个数字，而不是一遍又一遍地重新计算递归，从而产生更有效的解决方案。