题解 | #跳台阶#

因为是 dp ，所以先来划分子问题：

假设跳 $nn$ 个台阶的跳法总数为 $f_{n}f\_n$ ，

那么 $f_1=1f\_1=1$ （跳 $11$ 阶只有一种方法），$f_2=2f\_2=2$（跳 $22$ 阶有两种方法：1 1 和 2 ）。

尝试列出几个 $nn$ ：

$f_1=1f\_1=1$ ；

$f_2=2f\_2=2$ ；

$f_3=3f\_3=3$ ；

$f_4=5f\_4=5$ ；

$f_5=8f\_5=8$ ……

在列举过程中，我们会发现，每次跳跃方法数只取决于第一次选择 $11$ 还是 $22$：

如果选择先跳 $11$ 阶，就跟 $n-1n-1$ 阶时的跳跃方法数相同（这一跳消去了 $11$ 阶），也就是 $f_{n-1}f\_\{n-1\}$ ；

如果选择先跳 $22$ 阶，就跟 $n-2n-2$ 阶时的跳跃方法数相同（这一跳消去了 $22$ 阶），也就是 $f_{n-2}f\_\{n-2\}$ 。

实际跳台阶时，既可以选先跳 $11$ 阶，也可以选先跳 $22$ 阶，所以总跳法数是 $f_{n-1}+f_{n-2}f\_\{n-1\}+f\_\{n-2\}$ 。

得到了状态转移方程，就可以着手写程序了：

#include <bits/stdc++.h>
using namespace std;
long long a[50]; // 开 long long 防止溢出
int main(){
    int n; // 目标阶数
    cin>>n;
    a[1]=1; // 1 阶 1 种方法
    a[2]=2; // 2 阶 2 种方法
    for(int i=3;i<=n;i++){
        a[i]=a[i-1]+a[i-2]; // 状态转移
    }
    cout<<a[n]; // 输出
    return 0;
}

也可以选择递归：

#include <bits/stdc++.h>
using namespace std;
long long a[50];
long long s(int n){
  if(n==1||n==2){
  	return n;
  }else{
  	return s(n-2)+s(n-1); // 状态转移 & 递归
  }
}
int main(){
    int n;
    cin>>n;
    cout<<s(n);
    return 0;
}