2020 蓝桥杯大学 B 组省赛模拟赛（一）B.结果填空：爬楼梯

B.结果填空：爬楼梯

题目链接-爬楼梯

题目

蒜头君要爬楼梯。楼梯一共有 10 层台阶。因为腿长的限制，每次最多能上 4 层台阶。但是第 5,7 层楼梯坏掉了不能踩。求上楼梯的方案数

解题思路

dfs，dp都行
具体思路见代码
答案是72
注意：最开始蒜头君是在第0层而不是第一层

附上代码 代码1： dfs，因为第 5,7 层楼梯坏掉了不能踩且楼梯只有10层，所以递归到x=5或 x=7或x>10时直接返回 #include using namespace std; #define ll long long const int INF=0x3f3f3f; typedef pair PII; int ans; void dfs(int x){ if(x==5||x==7||x>10) return ;//不符合题意直接返回 if(x==10){//能到达第十层 ans++;//解的数目加1 return ; } for(int i=1;i<=4;i++)//每次最多只能上4层 dfs(x+i); } int main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); dfs(0);//从第0层开始 cout<<ans<<endl; return 0; } 代码2： 简单dp
1. dp[5]和dp[7]要直接跳过，因为不能踩上去
2. 因为最多只能上4层，所以其他阶梯的方案数由dp[i-1]+dp[i-2]+dp[i- 3]+dp[i-4]组成 #include using namespace std; #define ll long long const int INF=0x3f3f3f; typedef pair PII; int dp[15]; int main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); dp[0]=1;dp[1]=1; dp[2]=2;dp[3]=4; for(int i=4;i<=10;i++){ if(i==5||i==7) continue; dp[i]=dp[i]+dp[i-1]+dp[i-2]+dp[i-3]+dp[i-4]; } cout<<dp[10]<<endl; return 0; }
作者：Fiveneves

楼梯 蓝桥杯 大学