题解 | 跳台阶

动态规划三部曲(递推---->递推+记忆化搜索----->自底到顶的动态规划---->状态压缩)

1.递推(自顶到底）

本题可类比斐波那契，每次跳台阶与前一个和前两个有关所以到n目标位置有如下关系：f(n)=f(n-1)+f(n-2) f是计算方案数的函数，这是递推的核心，再加上边界讨论，。当n==1，代表前面就剩一个台阶了，只能跳一步，n==0代表结束了

所以有如下：

int solve(int n){

if(n==0)return 0;

if(n==1)return 1;

return f(n-1)+f(n-2);

}题目要求取模，补上即可，这里就不加了；

这个递推很容易超时，因为每次从n开始往前递推，总会有重复计算的部分比如我要算f(8),我需要f(7)和f(6),而f(7)又需要计算f(6)和f(5)，f(6)又需要计算f(5)和f(4)以此类推，我们可以发现这里每次递推都会有重复的部分。那我们把每次计算的结果放进一个数组里，然后下次用的的时候，如果有我们直接取出来，没有在计算这样不就可以大大减少复杂度了吗？

2.记忆化搜索

有了上面的思路，我们就可以创建一个数组dp[n+1]来记录跳到每个台阶的方案数，n+1是为了便于使用，这样第n个台阶就对应下表n了，那我们怎么判断是不是记录了呢，我们可以初始化特殊值，本题可以设置成-1，方案数是不可能为负的，这样就可以判断了，递推逻辑与上面基本一致，多了一步在每次递推前我都需要判断一下是否被记录，没有就递推完后记录一下。

int solve(int n,int dp[]){

if(n==0)return 0;

if(n==1)return 1;

if(dp[n]!=-1)return dp[n];

dp[n]=f(n-1,dp)+f(n-2,dp);

return dp[n];

}

其实这样就能过很多题目了，但却不是动态规划的标准写法，因为这是从顶到底的逻辑，顶是最复杂的，与下面的状态有关，相反底是最简单的情况，那我们是不是可以考虑从底到顶进行递推呢？

3.动态规划（从底到顶）

这个题，底就对应第一个台阶，这是起始点，那我们就从这里开始往后面推，因为后面的台阶是与前面有关的所以为了不出现重复的情况，我们同样需要一个dp数组来记录当前台阶的方案数，但这次是从起始点开始，同样开n+1，从底到顶的好处是前面的关系很清晰简单比如我们要到3阶梯，那么有两种方案从1或者从2，仍旧是f(n-1)+f(n-2)，可以发现递推逻辑几乎不变，我们可以让边界情况dp[0]为0代表无法从第零个台阶跳，因为不存在，dp[1]为1代表只能从第一个台阶跳这一种情况，逻辑跟上面类似。每次递推完记入dp最后输出n即可；

#include <iostream>

using namespace std;

#define mode 998244353

const int N=200005;

int main() {

int dp[N]={0};

int n;

cin>>n;

dp[1]=1;

for(int i=2;i<=n;i++){

dp[i]=(dp[i-1]+dp[i-2])%mode;

}

cout<<dp[n];

}

4.状态压缩

其实就是在3的基础上在空间上进行的优化，这里我们可以发现核心递推就是n-1和n-2那么我们可以用两个变量来替换，pre,cur；结果即为next,式子就是next=pre+cur;这是一次递推，下一次呢？那不就是整体往右移动一下吗？因为是从1开始的所以pre=0,cur=1;

#include <iostream>

using namespace std;

#define mode 998244353

int main() {

int n;

cin >> n;

// 状态压缩：只用两个变量

int prev = 0, curr = 1; // f(0)=0, f(1)=1

for (int i = 2; i <= n; i++) {

// 计算新状态

int next = (prev + curr) % mode;

// 滚动更新：向前移动窗口

prev = curr; // 原来的当前变成前一个

curr = next; // 新的计算值变成当前

}

cout << curr;

return 0;

}

以上我们可以发现，其实核心逻辑都一样只不过是动态规划多了一个dp容器来记录每次递推的值。