代码源129.走楼梯2
楼梯有 n 阶，上楼可以一步上一阶，也可以一步上二阶。
但你不能连续三步都走两阶，计算走到第n阶共有多少种不同的走法。
输入格式
一行，一个数字，表示n。
输出格式
输出走楼梯的方式总数。
样例输入
6
样例输出
12
数据规模
对于100%的数据，保证n≤50。
思路
DP问题
设 f[i][j] 表示已经到了第 i 个阶梯，且最近有走过 j 个二阶。那么就有 1 <= i <= n，因为不能连续走三个二阶，所以 j = 0, 1, 2。
假设现在的状态是在第 i 个阶梯，此时会有三种状态：f[i][0], f[i][1], f[i][2]。
即：
- 一步一阶登上第 i 阶
- 一步两阶，且第一次是一步两阶
- 一步两阶，且连续两次是一步两阶
1）那么 f[i][0] 是怎么转移过来的呢？因为此时的 j = 0，所以前一步到这一步一定是跨越了1个台阶过来的，那么前一种状态可以是任意的，即在 i - 1时， j 可以等于0，1，2都可以。所以状态转移方程为：f[i][j] = f[i-1][0] + f[i-1][1] + f[i-1][2] 。
2）对于 f[i][1]状态，此时 j = 1，最近的二阶台阶只有一个，所以一定是上一步通过走了一次二阶台阶到了现在的状态。即上一个状态的 j 一定等于 0（不能为1，为1的话，再走一次二阶台阶，那么目前的 j 就会为2）。状态转移方程为 f[i][1] = f[i-2][0] 。
3）对于 f[i][2] 状态，此时 j = 2，最近的二阶台阶走了两次，所以上一个状态一定是 j = 1，走了一个二阶台阶过来的。状态转移方程为 f[i][2] = f[i-2][1] 。
其他
当 i = 1 时，f[1][0] = f[0][0] + f[0][1] + f[0][2] ，因为 f[1][0] 只有一个台阶，所以等于 1，可以初始化设 f[0][0] = 1 ，这样 f[1][0] 可以为 1 了。
对于 2），3），因为有 i - 2 ，所以当 i >= 2 才需要更新 2），3）。
这样所以情况都包含进去了。
代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 60;
typedef long long LL;
LL f[N][3];
int main() {
int n;
cin >> n;
f[0][0] = 1;
for (int i = 1; i <= n; i++) {
f[i][0] = f[i-1][0] + f[i-1][1] + f[i-1][2];
if (i >= 2) {
f[i][1] = f[i-2][0];
f[i][2] = f[i-2][1];
}
}
cout << f[n][0] + f[n][1] + f[n][2] << endl;
return 0;
}
