解释这个动态编程攀爬n阶梯代码

Question

问题是

"你正在爬楼梯.每次你可以做一步或两步.楼梯有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)两步,总数是使用这些选项之一的方式的数量 - 因此总和).

如果你仔细观察 - 这也是一个众所周知的系列 - 斐波纳契数,解决方案只是计算每个数字,而不是一遍又一遍地重新计算递归,从而产生更有效的解决方案.