【蓝桥】动态规划-简单-破损的楼梯

 题目

解题思路 

 完整代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+9;
const long long p=1e9+7;
long long dp[N];//dp[i]表示走到第i级台阶的方案数
bool broken[N];//broken代表破损台阶的数组
int main()
{int n,m;cin>>n>>m;for(int i=1;i<=m;i++){int x;cin>>x;broken[x]=true;//如果第x级台阶破损了，那就设置成true}dp[0]=1;//第1级台阶比较特殊，因为它只有一种走法，就是从第0级迈到第1级，所以单独列出if(!broken[1])//如果第一级台阶没有破损{dp[1]=1;}
//破损默认dp[1]为0for(int i=2;i<=n;i++)//如果第1级台阶坏了，那就从第2级台阶开始{if(broken[i]){continue;}dp[i]=(dp[i-1]+dp[i-2])%p;//因为一次可以迈1—2个台阶（即可以从i-1或i-2级迈到第i级），所以第i级的方案数等于i-2级的方案数 + i-1级的方案数}cout<<dp[n]<<endl;return 0;
}

内存图助解

初始状态

在读取输入之前，flag 和 dp 数组都被初始化为 0，n 和 m 未赋值。

n: 未初始化
m: 未初始化flag: [0, 0, 0, 0, 0, 0, 0]  // flag[0] 到 flag[6]
dp:   [0, 0, 0, 0, 0, 0, 0]  // dp[0] 到 dp[6]

读取输入后的状态

读取 n = 6 和 m = 1 后，标记破损点 3。

n: 6
m: 1flag: [0, 0, 0, 1, 0, 0, 0]  // flag[3] 被标记为 1
dp:   [0, 0, 0, 0, 0, 0, 0]  // dp 数组未初始化

n: 6
m: 1flag: [0, 0, 0, 1, 0, 0, 0]
dp:   [1, 0, 0, 0, 0, 0, 0]  // dp[0] = 1，因为起点不是破损点

第一步：计算 dp[1]

• flag[1] = 0，不是破损点。

• dp[1] = dp[0] = 1

n: 6
m: 1flag: [0, 0, 0, 1, 0, 0, 0]
dp:   [1, 1, 0, 0, 0, 0, 0]

第二步：计算 dp[2]

• flag[2] = 0，不是破损点。

• dp[2] = dp[1] + dp[0] = 1 + 1 = 2

n: 6
m: 1flag: [0, 0, 0, 1, 0, 0, 0]
dp:   [1, 1, 2, 0, 0, 0, 0]

第三步：计算 dp[3]

• flag[3] = 1，是破损点，跳过。

• dp[3] = 0

n: 6
m: 1flag: [0, 0, 0, 1, 0, 0, 0]
dp:   [1, 1, 2, 0, 0, 0, 0]

最终结果为

n: 6
m: 1flag: [0, 0, 0, 1, 0, 0, 0]
dp:   [1, 1, 2, 0, 2, 2, 4]

输出 dp[6]，即到达终点的合法走法数量4