Go语言动态规划详解与使用方法

本文深入解析了Go语言中动态规划的核心实践要点，强调真正掌握动态规划不在于死记模板，而在于精准定义状态、严谨控制子问题边界，并特别警惕Go中map[int]int默认零值带来的逻辑陷阱；以爬楼梯问题变体为例，清晰展示了当步长扩展至1/2/3步时状态转移方程如何从dp[i]=dp[i-1]+dp[i-2]自然演进为dp[i]=dp[i-1]+dp[i-2]+dp[i-3]，同时详解基础情况（dp[0]=1, dp[1]=1, dp[2]=2）的合理性与数组长度需设为n+3的底层原因，助你写出健壮、可扩展的Go动态规划代码。

Go 里写动态规划，核心不是背模板，而是选对状态定义 + 控制好子问题边界 + 避开 map[int]int 的零值陷阱。

climbStairs 变体怎么改状态转移方程

经典爬楼梯（只跳 1 或 2 步）的转移是 dp[i] = dp[i-1] + dp[i-2]；但一旦支持跳 3 步，必须重审“最后一步可能从哪来”，不能硬套旧逻辑。新方程是 dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。

• 基础 case 必须对齐：dp[0] = 1（站在起点算 1 种方式），dp[1] = 1，dp[2] = 2；否则 i=3 时结果错
• 数组长度至少开 n+3，避免 dp[i-3] 越界；用切片推荐 make([]int, n+3)，再从 dp[0] 开始填
• n 时直接返回预设值，别进循环——漏掉会 panic 或算错

用 map[int]int 做 memo 为什么总出 bug

map[int]int 的零值是 0，而 memo[0] 合法解就是 1，if memo[n] != 0 这种判断在 n=0 时必然误判为“未计算”，导致无限递归或错结果。

• 正确写法是用 comma ok：if val, ok := memo[n]; ok { return val }
• 或者改用 map[int]*int，用 nil 表示未计算，非 nil 表示已缓存（适合真可能出现 0 的场景，比如最小花费）
• 更省事：用切片 memo := make([]int, n+1) + 单独 done := make([]bool, n+1) 标记是否计算过

二维 DP 如 LCS 怎么避免索引越界和乱码

LCS 的状态定义是 lcs[i][j] 表示 a[:i] 和 b[:j] 的最长公共子序列长度，这意味着二维切片必须开成 make([][]int, aLen+1) 和每行 make([]int, bLen+1)。

• 循环要写成 for i := 0; i 和 for j := 0; j ，漏掉等号会导致 lcs[aLen][bLen] 没更新，直接 panic
• 字符比较必须用 aRunes[i-1] == bRunes[j-1]，不能用 a[i] == b[j] —— Go 字符串下标取 byte，中文、emoji 会乱码或越界
• 输入含 Unicode 时，务必先转 []rune：aRunes := []rune(a)

什么时候该用 slice memo，什么时候该用 map memo

关键看 n 的范围和稀疏性。

• n 小且连续（比如楼梯 ≤ 10⁴）：用 []int 更快、省内存、索引安全；make([]int, n+1) 是常规操作
• n 极大但只查少数几个值（比如只调 CountWaysDP(1e6) 和 CountWaysDP(1e9)）：用 map[int]int 才有意义，否则 make([]int, 1e9+1) 直接 OOM
• map 有哈希开销，[]int 缓存友好；但 map 支持任意键，slice 要求键是连续非负整数

最易被忽略的是基础 case 与数组长度的耦合关系——比如跳 3 步时，dp[2] 必须手动设对，且 dp 切片长度必须 ≥ n+3，否则 dp[i-3] 在循环早期就 panic。这不是边界检查能绕过的，是状态定义本身决定的硬约束。

本篇关于《Go语言动态规划详解与使用方法》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于Golang的相关知识，请关注golang学习网公众号！