题目简述
有 $n$ 个台阶。从最下面走到最上面。
一步可以向上走 $1$ 个台阶或 $2$ 个台阶，不能连续两次都向上走 $2$ 个台阶。
请问从 $0$ 走到第 $n$ 级台阶一共有多少种方案。
数据规模与约定
- 对 $50\%$ 的测试点，$n \leq 5$。
- 对 $80\%$ 的测试点，$n \leq 20$。
- 对 $100\%$ 的测试点，$1 \leq n \leq 60$。
30分解法
分析题目，发现该题与 [P1255 数楼梯] 比较相似，属于记忆化搜索的问题。
不难发现一个性质，走到第 $n$ 级楼梯只有两种途径：
- 从第 $n-1$ 级向上走 $1$ 级
- 从第 $n-2$ 级向上走 $2$ 级
每一个节点都可由其子节点推导，我们设到第 $n$ 级的方案数为 $ dp_n $ 只需确定两个初始节点
$$dp_1=1, dp_2=2$$
便可求出所有结果，因此这是一个可以通过递归求解的问题
于是我们列出如下状态转移方程：$$ dp_n = dp_{n-1} + dp_{n-2} $$
并写出如下代码:
#include<bits/stdc++.h>
#define maxn 62
using namespace std;
signed main(){
int n;
cin >> n;
int dp[maxn];
dp[1] = 1, dp[2] = 2;
for(int i = 3; i <= n; ++ i)
dp[i] = dp[i-2]+2;
cout << dp[n];
return 0;
}
提交代码，发现只有 $30$ 分，原因很明显，正如题面所说
不能连续两次都向上走 $2$ 个台阶。
正解
既然不能连续两次走两个台阶，那么上述状态转移的过程必须分类讨论，
$dp_n$ 能由 $dp_{n-2}$ 转移当且仅当 $dp_{n-2}$ 的前一步只走了一步
我决定单独开两个数组，令 $dp1_n$ 和 $dp2_n$，分别记录
到达第 $n$ 级楼梯前最后一步走了 $1$ 步和 $2$ 步的方案数
并且保留之前所设 $dp_n$ 记录总方案数
这三个数组间存在三个相关联的性质：
- 第 $n-1$ 级向上走一步就到第 $n$ 级，即 $$dp1_n=dp_{n-1}$$
- 如果到第 $n-2$ 级前最后只走了 $1$ 步，那么可以一次性走 $2$ 级到达第 $n$ 级，即 $$dp2_n=dp1_{n-2}$$
- 爬到第 $n$ 级的方案总数等于最后一步为 $1$ 步与 $2$ 步方案数的总和，即 $$dp_n=dp1_n+dp2_n$$
化简可得
$$ dp_n = dp_{n-1} + dp_{n-3} $$
可以这么理解此式：
从第 $n-1$ 级向上走一步 和 从第 $n-3$ 级先向上一步再向上两步 这两种方案涵盖了所有情况
综上，只需心算并初始化最底层三级楼梯的数据
dp[1] = 1, dp[2] = 2, dp[3] = 3;
便可递推求出所有答案
最后需要注意的是，题目里 $n$ 的范围较大，需要开 long long 防止整型溢出
正解代码
#include<bits/stdc++.h>
#define int ll
#define maxn 62
using ll = long long;
using namespace std;
signed main(){
int n;
cin >> n;
int dp[maxn];
dp[1] = 1, dp[2] = 2, dp[3] = 3;
for(int i = 4; i <= n; ++ i)
dp[i] = dp[i-1] + dp[i-3];
cout << dp[n];
return 0;
}