题面
小明刚刚看完电影《第39级台阶》，离开电影院的时候，他数了数礼堂前的台阶数，恰好是39级!
站在台阶前，他突然又想着一个问题：
如果我每一步只能迈上1个或2个台阶。先迈左脚，然后左右交替，最后一步是迈右脚，也就是说一共要走偶数步。
那么，上完39级台阶，有多少种不同的上法呢？
请你利用计算机的优势，帮助小明寻找答案。
题解
DFS，DP
深度优先搜索（DFS）：从第一步开始，枚举每一步走一阶还是两阶，得到最后的结果即可。
动态规划（DP）：遍历每一个阶梯，计算当前阶梯从前一步转移过来的状态有多少种。
答案：
51167078
代码
- DFS
#include<iostream>
using namespace std;
int res;
void dfs(int k, int foot) { //foot：0为左脚，1为右脚
if (k > 39) return;
if (k == 39) {
if (foot == 1) res++;
return;
}
dfs(k + 1, !foot);
dfs(k + 2, !foot);
}
int main() {
dfs(0, 1);
cout << res << endl;
return 0;
}
- DP
#include<bits/stdc++.h>
using namespace std;
int f[45][2];
int main() {
//d[i][0] 表示以左脚走到第i阶的方案数
//d[i][1] 表示以右脚走到第i阶的方案数
f[0][1] = 1;
for (int i = 1; i <= 39; i++) {
//走一步到i的
if (f[i - 1][0]) f[i][1] += f[i - 1][0];
if (f[i - 1][1]) f[i][0] += f[i - 1][1];
//走两步到i的
if (i >= 2 && f[i - 2][0]) f[i][1] += f[i - 2][0];
if (i >= 2 && f[i - 2][1]) f[i][0] += f[i - 2][1];
}
cout << f[39][1] << endl;
return 0;
}
| 标题： | 2013年第四届蓝桥杯省赛-C. 第39级台阶 |
|---|---|
| 链接： | https://www.fightingok.cn/detail/161 |
| 更新： | 2022-09-18 22:44:13 |
| 版权： | 本文采用 CC BY-NC-SA 3.0 CN 协议进行许可 |