P4730 台阶问题（入门）

解题思路

小鹿上楼梯，一次可以迈 1 级，也可以迈 2 级。我们要算出上到第 n 级台阶一共有多少种走法。

先用小例子找规律。上第 1 级，只有 1 种走法（直接迈 1 级），记 f[1]=1。上第 2 级，可以一次迈 2 级，也可以分两次各迈 1 级，共 2 种走法，记 f[2]=2。上第 3 级呢？可以这样想：最后一步如果迈 1 级，那么前面已经上了 2 级，有 f[2]=2 种走法；最后一步如果迈 2 级，那么前面已经上了 1 级，有 f[1]=1 种走法。合起来 f[3]=2+1=3。

一般地，最后一步只有两种情况：迈 1 级或迈 2 级。所以上到第 n 级的走法数满足 f[n] = f[n-1] + f[n-2]，这就是著名的斐波那契数列。我们把 f[1]、f[2] 当作起点，从第 3 项开始一项一项往前推。n 最大只有 19，f[19]=6765，用 long long 保存绰绰有余。边界情况：n=1 时直接输出 1，n=2 时直接输出 2。

参考代码

// 台阶问题：上n级台阶，一步走1级或2级，统计总走法数（斐波那契递推）
#include <iostream>
int main(){
  long long a=1,b=2,c;  // a=f(1), b=f(2)
  int n,i;
  std::cin>>n;
  if(n==1){ std::cout<<1; return 0; }
  for(i=3;i<=n;i++){ c=a+b; a=b; b=c; }  // f[i]=f[i-1]+f[i-2]
  std::cout<<b;
  return 0;
}

复杂度分析

只用了一个循环从第 3 项推到第 n 项，每推一步做一次加法，所以时间是 O(n)。空间上只用了几个 long long 变量，是 O(1)。n 最多 19，循环 19 次就结束，运行速度非常快。