爬楼梯

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. **代码实现：**

def count_ways(N, M, bad_steps):
    MOD = int(1e9 + 7)
    dp = [0] * (N + 1)
    dp[0] = 1
    
    bad_set = set(bad_steps)
    
    if 1 not in bad_set:
        dp[1] = 1
    
    for i in range(2, N + 1):
        if i not in bad_set:
            dp[i] = (dp[i-1] + dp[i-2]) % MOD
    
    return dp[N]

# 示例调用
# N = 5, M = 2, bad_steps = [2, 4]
# 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 语言实现的方案：

#include <stdio.h>
#define MOD 1000000007

int countWays(int N, int M, int badSteps[]) {
    int dp[N + 1];
    for (int i = 0; i <= N; i++) {
        dp[i] = 0;
    }

    dp[0] = 1;
    int badSet[N + 1];
    for (int i = 0; i <= N; i++) {
        badSet[i] = 0;
    }
    
    for (int i = 0; i < M; i++) {
        badSet[badSteps[i]] = 1;
    }

    if (N >= 1 && badSet[1] == 0) {
        dp[1] = 1;
    }

    for (int i = 2; i <= N; i++) {
        if (badSet[i] == 0) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
        }
    }

    return dp[N];
}

int main() {
    int N, M;
    scanf("%d %d", &N, &M);

    int badSteps[M];
    for (int i = 0; i < M; i++) {
        scanf("%d", &badSteps[i]);
    }

    int result = countWays(N, M, badSteps);
    printf("%d\n", result);

    return 0;
}

### 代码说明：

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 语言）：**

#include <stdio.h>
#define MOD 1000000007

int countWays(int N, int M, int badSteps[]) {
    int dp[N + 1];
    int isBad[N + 1];

    // 初始化
    for (int i = 0; i <= N; i++) {
        dp[i] = 0;
        isBad[i] = 0;
    }

    // 标记坏台阶
    for (int i = 0; i < M; i++) {
        isBad[badSteps[i]] = 1;
    }

    // 动态规划初始条件
    dp[0] = 1;
    if (!isBad[1]) {
        dp[1] = 1;
    }

    // 计算到达每一级台阶的方法数
    for (int i = 2; i <= N; i++) {
        if (!isBad[i]) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
        }
    }

    return dp[N];
}

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 小助理，如未能正确解答您的问题，请继续追问。