爬楼梯

dinghuang

小蓝来到了一座高耸的楼梯前，楼梯共有 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
没有思路在，怎么思考，怎么写?

FishC

要解决这个问题，我们可以使用动态规划的方法。下面是简单步骤：

1. **定义状态：**
   - 定义 `dp[i]` 表示到达第 `i` 级台阶的方法数。

2. **初始化：**
   - `dp[0] = 1`，表示从第 0 级开始。
   - 如果第 1 级台阶没坏，`dp[1] = 1`，否则 `dp[1] = 0`。

3. **状态转移：**
   - 对于每一级台阶 `i`，若它是完好的，则：
     \[
     dp[i] = dp[i-1] + dp[i-2]
     \]
   - 如果当前台阶坏了，则 `dp[i] = 0`。

4. **考虑所有坏的台阶：**
   - 将坏掉的台阶赋值为 `0`，表示不能通过这些台阶。

5. **计算结果：**
   - 最终答案是 `dp[N] % (1e9 + 7)`。

6. **代码实现：**

1. def count_ways(N, M, bad_steps):
   
2.     MOD = int(1e9 + 7)
   
3.     dp = [0] * (N + 1)
   
4.     dp[0] = 1
   
5.    
   
6.     bad_set = set(bad_steps)
   
7.    
   
8.     if 1 not in bad_set:
   
9.         dp[1] = 1
   
10.    
    
11.     for i in range(2, N + 1):
    
12.         if i not in bad_set:
    
13.             dp[i] = (dp[i-1] + dp[i-2]) % MOD
    
14.    
    
15.     return dp[N]
    
16. 
    
17. # 示例调用
    
18. # N = 5, M = 2, bad_steps = [2, 4]
    
19. # print(count_ways(5, 2, [2, 4]))  # 输出结果

复制代码

通过这个方法，您可以计算出不踩坏台阶达到顶端的方案数量。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

dinghuang

FishC 发表于 2024-10-28 20:55
要解决这个问题，我们可以使用动态规划的方法。下面是简单步骤：

1. **定义状态：**

c 语言写法

FishC

dinghuang 发表于 2024-10-28 21:22
c 语言写法

下面是使用 C 语言实现的方案：

1. #include <stdio.h>
   
2. #define MOD 1000000007
   
3. 
   
4. int countWays(int N, int M, int badSteps[]) {
   
5.     int dp[N + 1];
   
6.     for (int i = 0; i <= N; i++) {
   
7.         dp[i] = 0;
   
8.     }
   
9. 
   
10.     dp[0] = 1;
    
11.     int badSet[N + 1];
    
12.     for (int i = 0; i <= N; i++) {
    
13.         badSet[i] = 0;
    
14.     }
    
15.    
    
16.     for (int i = 0; i < M; i++) {
    
17.         badSet[badSteps[i]] = 1;
    
18.     }
    
19. 
    
20.     if (N >= 1 && badSet[1] == 0) {
    
21.         dp[1] = 1;
    
22.     }
    
23. 
    
24.     for (int i = 2; i <= N; i++) {
    
25.         if (badSet[i] == 0) {
    
26.             dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
    
27.         }
    
28.     }
    
29. 
    
30.     return dp[N];
    
31. }
    
32. 
    
33. int main() {
    
34.     int N, M;
    
35.     scanf("%d %d", &N, &M);
    
36. 
    
37.     int badSteps[M];
    
38.     for (int i = 0; i < M; i++) {
    
39.         scanf("%d", &badSteps[i]);
    
40.     }
    
41. 
    
42.     int result = countWays(N, M, badSteps);
    
43.     printf("%d\n", result);
    
44. 
    
45.     return 0;
    
46. }

复制代码

### 代码说明：

1. **宏定义：**
   - `#define MOD 1000000007`：定义取模常数。

2. **函数 `countWays`：**
   - `dp[N + 1]`：用于存储到达每一级的方法数。
   - `badSet[N + 1]`：记录哪些台阶是坏的，用于快速检查。
   - 从第 2 级开始，根据状态转移方程更新 `dp`。

3. **主程序：**
   - 输入 `N` 和 `M`，以及坏台阶的序号。
   - 调用 `countWays` 函数，并输出结果。

希望这个代码能帮助您理解如何实现爬楼梯问题。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

dinghuang

FishC 发表于 2024-10-28 21:22
下面是使用 C 语言实现的方案：

没有理解能不能详细说一下思路，是递归但不理解，他求的不是方法吗，递归是个漏洞

FishC

dinghuang 发表于 2024-10-28 21:36
没有理解能不能详细说一下思路，是递归但不理解，他求 ...

好的，我们使用递归思想结合动态规划来解决这个问题。动态规划可以避免重复计算，提高效率。

### 思路解析：

1. **基础状态：**
   - 如果有坏台阶，我们不能在这些台阶上。

2. **递归关系：**
   - 对于到达第 `i` 级台阶，只有两种方式：
     1. 从第 `i-1` 级迈一步上来。
     2. 从第 `i-2` 级迈两步上来。
   - 如果这些台阶不是坏的，我们求和：
     \[
     \text{dp}[i] = \text{dp}[i-1] + \text{dp}[i-2]
     \]
   - 如果台阶坏了，则 `dp[i] = 0`。

3. **动态规划初始化：**
   - `dp[0] = 1`，表示从起点出发的方式。
   - `dp[1] = 1`，如果第 1 级台阶不是坏的。

4. **动态规划过程：**
   - 从第 2 级台阶开始，一直计算到第 N 级台阶。

5. **代码实现（C 语言）：**

1. #include <stdio.h>
   
2. #define MOD 1000000007
   
3. 
   
4. int countWays(int N, int M, int badSteps[]) {
   
5.     int dp[N + 1];
   
6.     int isBad[N + 1];
   
7. 
   
8.     // 初始化
   
9.     for (int i = 0; i <= N; i++) {
   
10.         dp[i] = 0;
    
11.         isBad[i] = 0;
    
12.     }
    
13. 
    
14.     // 标记坏台阶
    
15.     for (int i = 0; i < M; i++) {
    
16.         isBad[badSteps[i]] = 1;
    
17.     }
    
18. 
    
19.     // 动态规划初始条件
    
20.     dp[0] = 1;
    
21.     if (!isBad[1]) {
    
22.         dp[1] = 1;
    
23.     }
    
24. 
    
25.     // 计算到达每一级台阶的方法数
    
26.     for (int i = 2; i <= N; i++) {
    
27.         if (!isBad[i]) {
    
28.             dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
    
29.         }
    
30.     }
    
31. 
    
32.     return dp[N];
    
33. }
    
34. 
    
35. int main() {
    
36.     int N = 5; // 总台阶数
    
37.     int M = 2; // 坏台阶数
    
38.     int badSteps[] = {2, 4}; // 坏台阶位置
    
39. 
    
40.     int result = countWays(N, M, badSteps);
    
41.     printf("不踩坏台阶到达顶端的方法数: %d\n", result);
    
42.    
    
43.     return 0;
    
44. }

复制代码

### 关键点：
- 本方法避免了递归带来的重复计算，效率更高。
- 使用 `MOD` 是为了防止大数问题，保证结果在合理范围内。
- `dp` 数组存储到达每一级的方法数，`isBad` 数组用来标记坏台阶。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。