破损的楼梯

本文主要是介绍破损的楼梯，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

分析：

也就是说，每一次步长是 1或2，如果a[i]是破损的楼梯的话，那么不能走。
所要解决的问题是，到达楼顶的方案数对1e9+7取模。
到达每一个楼梯 i 的前提是 要么从 i-1 或 i-2 的位置上来的，如果 i 的位置的值=0，则表示是坏的。
可以有状态 dp[i] 表示走到第 i 层楼梯的方案数。
所以，dp[i]=dp[i-1]+dp[i-2]
用 dp 数组来记录走动第 i 层的方案数。

示例代码：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll p = 1e9+7;
const ll N = 1e5+5;
ll dp[N],a[N];
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int n,m;cin>>n>>m;for(int i=1;i<=m;i++){int nm;cin>>nm;a[nm]=1;}// dp[i] = dp[i-1] +dp[i-2]dp[0]=1;if(!a[1])dp[1]=1;for(int i=2;i<=n;i++){if(a[i])continue;//dp[i]=0dp[i]=(dp[i-1]+dp[i-2])%p;}cout<<dp[n];return 0;
}

注意：

for(int i=2;i<=n;i++){if(a[i])continue;//dp[i]=0dp[i]=dp[i-1]+dp[i-2];
}
cout<<dp[n]%p;//这样写只能过10%的案例，因为结果很大，导致最后取模出现问题，所以要计算一次，取模一次

这篇关于破损的楼梯的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---