学动态规划真的是比较令人头大，概念挺难理解的说实话，要反复的咀嚼才能明白一二，记录一下我的学习成果。

一、概念

  • ✅ 转移方程：根据步数选项写出 dp[i] = dp[i-a] + dp[i-b]
  • ✅ 边界条件：推不动的手动给，到不了的是 0，dp[0]=1 是约定
  • ✅ 负数处理：i-k < 0 就扔掉
  • ✅ 特殊处理：坏台阶强制 dp=0
  • ✅ i 和 n 的区别：i 是变量，n 是具体目标

二、例子

用爬楼梯的例子来辅助理解这些概念

题目条件：

  • 楼梯总高为 n=4（地面是 0，目标阶梯是 4）
  • 跨步规则：只能跨 1 步 或 2 步（a=1 or b=2）
  • 其中阶梯 3 是坏的

1、定义 dp[i] 到底是什么？

从地面出发刚好到第 i 阶时，一共有多少种不同的走法。注意是刚好，超过的不行。

2、转移方程（最后一步怎么来的 — 逆向思维）

dp[i] = dp[i-1] + dp[i-2]

想象你处在第 i 阶，是怎么跨上来的？因为规则规定只能跨 1 步 or 2 步，只有两种方法：

  • 从 i-1 跨一步到 i
  • 从 i-2 跨两步到 i

既然到达 i-1 有 dp[i-1] 种走法，到达 i-2 有 dp[i-2] 种走法，所以到达 i 一共有 dp[i-1] + dp[i-2] 种走法。

3、边界条件与负数处理（推不动就手动给）

问题来了：假设我们要到 1 层，带入公式 dp[1] = dp[0] + dp[-1]，这里的 -1 是不合理的——我要到第 i 阶层，要么 0 种方法，要么 k 种方法，楼梯没有负数阶级！

处理原则：

  • 当计算 dp[i] 时，如果 i - 跨步数 < 0，说明这一步根本不存在，直接丢弃，不加这一项
  • 对于地面（第 0 层），它没办法用公式推出来，所以手动约定 dp[0]=1——想象不动也能到第零层，所以有一种方法。如果没有这个 1，后面所有的数都会变成 0

加上负数保护后，通用公式变成：

1
dp[i] = (i >= 1 ? dp[i-1] : 0) + (i >= 2 ? dp[i-2] : 0)

4、烂掉的阶层特殊处理

比如题目中烂掉的台阶 3，意味着不能踩上去，踩上去等于踏空，所以必须把 dp[3] 强行写成 0，即 bad 阶梯 = 0。

5、彻底搞清楚 i 和 n 的区别（附带完整手工推演）

  • n 是终点编号（常数），循环到 n 就停
  • i 是循环变量，代表我们当前正在计算哪个台阶

对着 n=4, a=1, b=2, bad={3} 一步步手算：

i 是否为坏台阶？ 计算过程 dp[i] 结果 解释
0 否（地面没坏） 手动约定 1 站在起点，算 1 种走法
1 否 dp[1] = dp[0] + dp[-1]（扔掉负的）= 1 + 0 1 路径：0→1
2 否 dp[2] = dp[1] + dp[0] = 1 + 1 2 路径：0→1→2；0→2
3 是（坏） 强制置零，不计算 0 所有到此的路径全作废
4 否（终点） dp[4] = dp[3] + dp[2] = 0 + 2 2 只能通过 2 跨 2 步上来。路径：0→1→2→4；0→2→4

最终输出 dp[4] = 2

6、如果起点（0）或终点（n）是坏台阶怎么办？

这是边界条件里的特殊边界，题目明确说了可能包含 0 和 n。

  • 如果 0 是坏的：还没开始就摔了。此时 dp[0] 必须是 0，不能是 1。后面的数再怎么加全是 0，输出 0。（符合常识）
  • 如果 n 是坏的：终点都坏了，目标平台根本不能踩。在循环到 i=n 时，强制 dp[n]=0，输出 0。（符合常识）

三、总结

概念 要点
转移方程 站在终点看最后一步，倒推来源，加和
负数处理 下标小于 0 的直接无视，不加这一项
dp[0] 默认是 1，但前提是 0 没坏（坏了就是 0）
坏台阶 计算时先判断坏没坏，坏了立刻 dp[i]=0 并跳过，绝对不能让它把数值往后传
下标区分 n 是终点常量，i 是循环变量，答案永远在 dp[n]