问题描述
小明正在爬一个有 n 级台阶的楼梯，但是他的体力有限，每次只能爬 1 级或者 2 级台阶。更特别的是，楼梯的某些台阶是坏的，小明不能踩上去。小明的目标是爬到楼梯的顶部（第 n 级台阶），但必须避开所有坏掉的台阶。现在，请你帮助小明计算，在避开所有坏台阶的情况下，他有多少种不同的方式可以爬到楼梯顶部。
注意：
- 楼梯台阶编号从 0 开始（0 表示地面起点）到 n 结束（n 表示顶部终点）
- 共有 n+1 个位置（0, 1, 2, …, n），但只有 n 级实际台阶（从 1 到 n）
- 坏台阶列表 bad 中的元素表示不能踩的台阶编号（在 1 到 n-1 范围内）
要求：
测试样例
样例1：
输入：n = 3, bad = [2] 输出：1 解释：台阶编号为 0（起点）、1、2、3（终点）。第 2 级台阶是坏的。 有效路径：
- 0 → 1 → 3（先爬1级到1，再爬2级到3） 无效路径：
- 0 → 2 → 3（第2级是坏的）
- 0 → 1 → 2 → 3（经过坏台阶2） 所以只有 1 种方式。
样例2：
输入：n = 4, bad = [1, 3] 输出：1 解释：台阶编号为 0、1、2、3、4。第 1 级和第 3 级是坏的。 有效路径：
- 0 → 2 → 4（先爬2级到2，再爬2级到4） 无效路径：
- 0 → 1 → …（第1级坏）
- 0 → 2 → 3 → 4（第3级坏） 所以只有 1 种方式。
样例3：
输入：n = 5, bad = [] 输出：8 解释：没有坏台阶，这就是经典的爬楼梯问题。爬到第 5 级的方式数量是 8（斐波那契数列：1,2,3,5,8）。 有效路径包括所有可能的 1 步和 2 步组合。
样例4：
输入：n = 2, bad = [] 输出：2 解释：台阶编号为 0、1、2。没有坏台阶。 有效路径：
- 0 → 1 → 2（两次1步）
- 0 → 2（一次2步） 所以有 2 种方式。
样例5：
输入：n = 3, bad = [] 输出：3 解释：台阶编号为 0、1、2、3。没有坏台阶。 有效路径：
- 0 → 1 → 2 → 3
- 0 → 1 → 3
- 0 → 2 → 3 所以有 3 种方式。
约束条件
- 1 ≤ n ≤ 1000
- 0 ≤ len(bad) ≤ n
- bad 中的元素互不相同，且都在 [1, n-1] 范围内（坏台阶不会包括第 0 级或第 n 级）
- 答案保证在 32 位有符号整数范围内
解题提示
可以使用动态规划：
- 设 dp[i] 表示到达第 i 级台阶的方式数
- 初始化：dp[0] = 1（起点）
- 对于每个位置 i（从 1 到 n）：
- 如果 i 是坏台阶，则 dp[i] = 0
- 否则，dp[i] = dp[i-1] + dp[i-2]（可以从 i-1 爬 1 步或从 i-2 爬 2 步到达）
- 注意处理边界条件（i-1 和 i-2 需要大于等于 0）
程序代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int climbStairs(int n, int* bad, int badSize) {
// 标记坏台阶
int* isBad = (int*)calloc(n + 1, sizeof(int));
for (int i = 0; i < badSize; i++) {
isBad[bad[i]] = 1;
}
// dp[i] 表示到达第 i 级台阶的方式数
int* dp = (int*)malloc((n + 1) * sizeof(int));
dp[0] = 1;
for (int i = 1; i <= n; i++) {
if (isBad[i]) {
dp[i] = 0;
} else {
dp[i] = 0;
if (i – 1 >= 0) dp[i] += dp[i – 1];
if (i – 2 >= 0) dp[i] += dp[i – 2];
}
}
int result = dp[n];
free(dp);
free(isBad);
return result;
}
int main() {
int bad1[] = {2};
printf("%d\\n", climbStairs(3, bad1, 1)); // 1
int bad2[] = {1, 3};
printf("%d\\n", climbStairs(4, bad2, 2)); // 1
int bad3[] = {};
printf("%d\\n", climbStairs(5, bad3, 0)); // 8
printf("%d\\n", climbStairs(2, bad3, 0)); // 2
printf("%d\\n", climbStairs(3, bad3, 0)); // 3
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int climbStairs(int n, int* bad, int badSize) {
// 标记坏台阶
int* isBad = (int*)calloc(n + 1, sizeof(int));
for (int i = 0; i < badSize; i++) {
isBad[bad[i]] = 1;
}
// dp[i] 表示到达第 i 级台阶的方式数
int* dp = (int*)malloc((n + 1) * sizeof(int));
dp[0] = 1;
for (int i = 1; i <= n; i++) {
if (isBad[i]) {
dp[i] = 0;
} else {
dp[i] = 0;
if (i – 1 >= 0) dp[i] += dp[i – 1];
if (i – 2 >= 0) dp[i] += dp[i – 2];
}
}
int result = dp[n];
free(dp);
free(isBad);
return result;
}
int main() {
int bad1[] = {2};
printf("%d\\n", climbStairs(3, bad1, 1)); // 1
int bad2[] = {1, 3};
printf("%d\\n", climbStairs(4, bad2, 2)); // 1
int bad3[] = {};
printf("%d\\n", climbStairs(5, bad3, 0)); // 8
printf("%d\\n", climbStairs(2, bad3, 0)); // 2
printf("%d\\n", climbStairs(3, bad3, 0)); // 3
return 0;
}
运行结果
