爬楼梯
小蓝来到了一座高耸的楼梯前，楼梯共有 N 级台阶，从第 0 级台阶出发。小蓝每次可以迈上 1 级或 2 级台阶。但是，楼梯上的第a1 级、第 a2 级、第
a3 级，以此类推，共 M级台阶的台阶面已经坏了，不能踩上去。
现在，小蓝想要到达楼梯的顶端，也就是第 N级台阶，但他不能踩到坏了的
台阶上。请问他有多少种不踩坏了的台阶到达顶
端的方案数？
由于方案数很大，请输出其对 1e9+7取模的结果。
输入格式：第一行包含两个正整数 N（1≤N≤1e5 ）和 M（0≤M≤N），表示楼
梯的总级数和坏了的台阶数。接下来一行，包含 M 个正整数 a1,a2,…,aM（1
≤a1<a2<a3<aM≤N），表示坏掉的台阶的编号。
输出格式：
输出一个整数，表示小蓝到达楼梯顶端的方案数，对 1e9+7取模。
样例输入
6 1
3
样例输出
4
没有思路在，怎么思考，怎么写? 要解决这个问题，我们可以使用动态规划的方法。下面是简单步骤：
1. **定义状态：**
- 定义 `dp` 表示到达第 `i` 级台阶的方法数。
2. **初始化：**
- `dp = 1`，表示从第 0 级开始。
- 如果第 1 级台阶没坏，`dp = 1`，否则 `dp = 0`。
3. **状态转移：**
- 对于每一级台阶 `i`，若它是完好的，则：
\[
dp = dp + dp
\]
- 如果当前台阶坏了，则 `dp = 0`。
4. **考虑所有坏的台阶：**
- 将坏掉的台阶赋值为 `0`，表示不能通过这些台阶。
5. **计算结果：**
- 最终答案是 `dp % (1e9 + 7)`。
6. **代码实现：**
def count_ways(N, M, bad_steps):
MOD = int(1e9 + 7)
dp = * (N + 1)
dp = 1
bad_set = set(bad_steps)
if 1 not in bad_set:
dp = 1
for i in range(2, N + 1):
if i not in bad_set:
dp = (dp + dp) % MOD
return dp
# 示例调用
# N = 5, M = 2, bad_steps =
# print(count_ways(5, 2, ))# 输出结果
通过这个方法，您可以计算出不踩坏台阶达到顶端的方案数量。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 FishC 发表于 2024-10-28 20:55
要解决这个问题，我们可以使用动态规划的方法。下面是简单步骤：
1. **定义状态：**
c 语言写法 dinghuang 发表于 2024-10-28 21:22
c 语言写法
下面是使用 C 语言实现的方案：
#include <stdio.h>
#define MOD 1000000007
int countWays(int N, int M, int badSteps[]) {
int dp;
for (int i = 0; i <= N; i++) {
dp = 0;
}
dp = 1;
int badSet;
for (int i = 0; i <= N; i++) {
badSet = 0;
}
for (int i = 0; i < M; i++) {
badSet] = 1;
}
if (N >= 1 && badSet == 0) {
dp = 1;
}
for (int i = 2; i <= N; i++) {
if (badSet == 0) {
dp = (dp + dp) % MOD;
}
}
return dp;
}
int main() {
int N, M;
scanf("%d %d", &N, &M);
int badSteps;
for (int i = 0; i < M; i++) {
scanf("%d", &badSteps);
}
int result = countWays(N, M, badSteps);
printf("%d\n", result);
return 0;
}
### 代码说明：
1. **宏定义：**
- `#define MOD 1000000007`：定义取模常数。
2. **函数 `countWays`：**
- `dp`：用于存储到达每一级的方法数。
- `badSet`：记录哪些台阶是坏的，用于快速检查。
- 从第 2 级开始，根据状态转移方程更新 `dp`。
3. **主程序：**
- 输入 `N` 和 `M`，以及坏台阶的序号。
- 调用 `countWays` 函数，并输出结果。
希望这个代码能帮助您理解如何实现爬楼梯问题。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 FishC 发表于 2024-10-28 21:22
下面是使用 C 语言实现的方案：
没有理解能不能详细说一下思路，是递归但不理解，他求的不是方法吗，递归是个漏洞{:5_104:} dinghuang 发表于 2024-10-28 21:36
没有理解能不能详细说一下思路，是递归但不理解，他求 ...
好的，我们使用递归思想结合动态规划来解决这个问题。动态规划可以避免重复计算，提高效率。
### 思路解析：
1. **基础状态：**
- 如果有坏台阶，我们不能在这些台阶上。
2. **递归关系：**
- 对于到达第 `i` 级台阶，只有两种方式：
1. 从第 `i-1` 级迈一步上来。
2. 从第 `i-2` 级迈两步上来。
- 如果这些台阶不是坏的，我们求和：
\[
\text{dp} = \text{dp} + \text{dp}
\]
- 如果台阶坏了，则 `dp = 0`。
3. **动态规划初始化：**
- `dp = 1`，表示从起点出发的方式。
- `dp = 1`，如果第 1 级台阶不是坏的。
4. **动态规划过程：**
- 从第 2 级台阶开始，一直计算到第 N 级台阶。
5. **代码实现（C 语言）：**
#include <stdio.h>
#define MOD 1000000007
int countWays(int N, int M, int badSteps[]) {
int dp;
int isBad;
// 初始化
for (int i = 0; i <= N; i++) {
dp = 0;
isBad = 0;
}
// 标记坏台阶
for (int i = 0; i < M; i++) {
isBad] = 1;
}
// 动态规划初始条件
dp = 1;
if (!isBad) {
dp = 1;
}
// 计算到达每一级台阶的方法数
for (int i = 2; i <= N; i++) {
if (!isBad) {
dp = (dp + dp) % MOD;
}
}
return dp;
}
int main() {
int N = 5; // 总台阶数
int M = 2; // 坏台阶数
int badSteps[] = {2, 4}; // 坏台阶位置
int result = countWays(N, M, badSteps);
printf("不踩坏台阶到达顶端的方法数: %d\n", result);
return 0;
}
### 关键点：
- 本方法避免了递归带来的重复计算，效率更高。
- 使用 `MOD` 是为了防止大数问题，保证结果在合理范围内。
- `dp` 数组存储到达每一级的方法数，`isBad` 数组用来标记坏台阶。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
页:
[1]