楼梯有 nnn 阶，上楼可以一步上一阶，也可以一步上二阶。

但你不能连续三步都走两阶，计算走到第nnn阶共有多少种不同的走法。

输入格式

一行，一个数字，表示nnn。

输出格式

输出走楼梯的方式总数。

样例输入

6

样例输出

12

数据规模

对于100100%100的数据，保证n≤50n≤50n≤50。

解题思路：

需要遍历每一种情况，很容易想到DP

如果没有限制“不能连续三步都走两阶”，本题就是简单的兔子数列

dp[0] = 1;//简单的初始化条件，台阶数为0，只有一种可能for (int i = 1; i <= max_step; i++)dp[i] = dp[i - 1] + dp[i - 2];

多了限制，自然就少了可能

那么尝试用排除法

需要排除走666、888、101010、141414、.........，显然需要排除的情况太多了

所以我们采用正难则反的思路，正面求解

对于每一步，我们有三种选择（只有三种情况，不难证明）：111、222、444

但是需要考虑限制，所以有以下几种情况

（1）当前走了111步，到达此处的方式不受限制

（2）当前走了222步，所以我们只能通过走111步的方式到达此处

（3）当前走了444步，所以我们只能通过走111步的方式到达此处

很简单，于是我们根据这个思路写出代码

int dp[max_step + 1] = { 0 };//存储数据含义：到达当前位置之后的可能数
bool disable[max_step + 1][3] = { false };//限制标记
int step[3] =  { 1,2,4 };dp[0] = 1;//简单的初始化条件，台阶数为0，只有一种可能for (int i = 1; i <= max_step; i++) {for (int j = 0; j < 3; j++) {if (!disable[i - step[j]][j]) {dp[i] += dp[i - step[j]];if (j != 0) disable[i][1] = disable[i][2] = true;//只能通过走1步的方式到达}}
}

结束了？当然没有，这个思路是有一点瑕疵的

假如当前有444级台阶，有几种方法？

很快你就会回答有555种，但是计算机会回答有444种

那么是哪一种可能性被漏掉了呢？

1 1 1 1
2 1 1
1 2 1
1 1 2
2 2

是第三种可能消失了

因为我们被禁止跳222级台阶到达dp[2]，但是这不是应该被禁止的吗？

我们要禁止的是跳222级、跳444级连续选择

但是上面的方法会导致跳222级之后跳111级的可能也被去除了，所以我们修改代码，把跳1,2,41, 2, 41,2,4级的情况分开存储

int dp[max_n + 1][3];//存储的数据含义：以方式j到达当前位置之后的可能数
int step[3] = { 1,2,4 };dp[0][0] = dp[0][1] = dp[0][2] = 1;for (int i = 1; i <= max_step; i++) {for (int j = 0; j < 3; j++) {dp[i][0] += dp[i - step[j]][j];if (j == 1) dp[i][j] += dp[i - step[0]][0];else if (j == 2) dp[i][j] += dp[i - step[0]][0];}
}

最后，AC代码如下

#include 
#include 
using namespace std;
const int max_n = 50;
const int bias = 4;//加上偏置量，防止数组越界long long dp[max_n + 1 + bias][3];
int step[3] = { 1,2,4 };int main() {int n;cin >> n;dp[0 + bias][0] = dp[0 + bias][1] = dp[0 + bias][2] = 1;for (int i = 1 + bias; i <= n + bias; i++) {for (int j = 0; j < 3; j++) {dp[i][0] += dp[i - step[j]][j];if (j == 0) {dp[i][1] += dp[i - step[j]][j];dp[i][2] += dp[i - step[j]][j];}}}cout << dp[n + bias][0];return 0;
}