47道DP题，一次过74%，翻车姿势比想象中离谱
上周我用 GPT-5.6 API 跑了 47 道 DP 题，翻车 12 次。
最离谱的一道背包题，它给我整了个 O(n³) 的解，跑完直接超时。我盯着屏幕愣了几秒——这复杂度你自己不觉得离谱吗？但话说回来，剩下 35 道里有 8 道的代码质量比我手写的还干净，变量命名、注释、边界处理都很到位。这就让我有点纠结了，到底靠不靠谱？干脆正经测一次。
评测环境
先说配置。GPT-5.6 的 standard 接口，temperature 设的 0.3。设太低代码太死板，设高了容易放飞自我，0.3 是我试了几轮之后觉得比较稳的值。max_tokens 给了 4096，够用。
题库是 LeetCode 上 rating 1800 以上的 DP 题，外加几道 ACM 区域赛真题，总共 47 道。覆盖了线性 DP、区间 DP、树形 DP、状压 DP、数位 DP 这几个大类。本来还想加几道概率 DP，但题太少凑不够，算了。
prompt 设计上我踩了个坑。一开始直接把题目描述甩过去让它写代码，结果它经常忽略边界条件——比如空数组、单元素这种 edge case。后来我改成三步走：先让它分析题目识别 DP 类型，再推导状态定义和转移方程，最后才生成代码。准确率直接从 62% 拉到 74%。这个提升比我预想的大，大概 prompt 工程确实有点东西。
等等，这里我要更正一下——准确率 74% 是"一次通过率"，也就是代码扔进 LeetCode 直接 AC 的比例。如果算上两轮内修正成功的，整体能到 85% 左右。后面会细说。
具体案例
案例一：编辑距离
这道经典题 GPT-5.6 处理得很漂亮。它先识别出是二维 DP，然后给出 dp[i][j] 表示 word1 前 i 个字符转换到 word2 前 j 个字符的最少操作数。转移方程写得清楚，空字符串的边界也自动处理了。代码跑完所有 test case 一遍过，复杂度分析也对。
有意思的是它在注释里写了句"可以考虑用滚动数组优化到 O(n) 空间"。这个细节让我挺意外——之前的版本很少主动提优化方向。我记得 GPT-4 那会儿，你不问它就不说，跟挤牙膏似的。
案例二：正则表达式匹配
翻车了。
这道 hard 题是 '.' 和 '' 的正则匹配。GPT-5.6 第一次给出的状态定义是对的，但处理 '' 匹配零次或多次的逻辑时，转移方程漏了一种情况：当 p[j-1] 是 '*' 且 p[j-2] 匹配 s[i-1] 时，应该考虑 dp[i-1][j] 这个状态，但它只写了 dp[i][j-2]。
我让它 self-debug，来回改了三次才改对。这个过程中我发现一个问题：GPT-5.6 对"选择"类 DP 的推理还是不够稳。每个状态有多个分支决策的时候，它容易漏分支。感觉像是推理链条一长，注意力就散了。
嗯...这个比较复杂。我觉得本质上是大模型对"或"逻辑的处理还是有短板，它倾向于走最直觉的那条路径，其他可能性就被忽略了。
案例三：旅行商问题
惊喜。
这道状压 DP 我以为它会直接跪，结果给出了一个相当工整的解法。dp[mask][i] 表示访问过的城市集合为 mask、当前在城市 i 的最短路径。状态转移的枚举顺序也写对了——先枚举 mask 再枚举当前节点和目标节点。这个顺序搞错的话结果会偏小，属于那种"代码能跑但答案不对"的隐蔽 bug，它居然没踩。
唯一的小毛病是初始化的时候把 dp[1][0] 设成 0、其他设成无穷大，但没提如果某些状态不可达该怎么处理。不过代码能 AC 所有测试点，这个表现已经超出我预期了。说实话我自己写这道题第一次也忘了处理不可达状态，还是 WA 了一发才反应过来。
数据说话
47 道题的结果我整理了一下：
- 线性 DP（15 题）：一次通过率 80%，两次内修正率 93%
- 区间 DP（8 题）：一次通过率 50%，两次内修正率 75%
- 树形 DP（7 题）：一次通过率 57%，两次内修正率 71%
- 状压 DP（9 题）：一次通过率 44%，两次内修正率 67%
- 数位 DP（5 题）：一次通过率 40%，两次内修正率 60%
- 背包变种（3 题）：一次通过率 100%
规律很明显。结构固定的 DP（线性、背包）表现好，状态空间复杂或者需要多维度决策的（状压、数位）容易翻。另外题目描述越接近自然语言的，它理解得越好；数学符号多的、需要从公式反推意图的题，准确率明显下降。我觉得这个跟训练数据分布有关系——LeetCode 题解区大部分是文字描述思路，纯公式推导的内容少。
踩坑记录
说几个实际碰到的问题，如果你要用 GPT-5.6 刷题或者做代码生成可以参考：
坑 1：边界初始化经常漏
好几道题它把 dp 数组的递推逻辑写对了，但 base case 初始化不完整。比如最长回文子序列那题，它只初始化了长度为 1 的情况，长度为 2 的没处理，导致偶数长度回文全挂。后来我在 prompt 里专门加了一句"请检查所有边界条件的初始化"，情况好了一些，但偶尔还是会漏。据我了解，这个问题在 GPT-4 时代就有，5.6 改进了但没根治。
坑 2：空间优化容易引入 bug
有次我让它把一道题的 O(n²) 空间优化到 O(n)，它用了滚动数组但循环顺序没调整，导致状态被覆盖。这种错误很隐蔽，不跑测试根本看不出来。建议如果要用它做空间优化，一定要求它解释为什么循环顺序要改成这样。别光看代码，看解释。
坑 3：对约束条件不敏感
一道题里 n 的范围是 10^5，它给的解法是 O(n²)，显然过不了。我追问了一句"n 最大 10 万，这个复杂度能过吗"，它才反应过来改成 O(n log n)。所以用的时候最好把数据范围也塞进 prompt 里，别指望它自己注意。
哦对了，还有一个不算坑但挺烦的事：GPT-5.6 偶尔会在代码里用一些奇怪的变量名，比如 t、cur、tmp 这种。读起来费劲。你得手动 rename 一遍，或者直接在 prompt 里要求"变量命名请使用有意义的英文单词"。
跟 GPT-4 和 Claude 3.5 的简单对比
我拿同样的 20 道题测了 GPT-4 和 Claude 3.5 Sonnet（2024 年 10 月那个版本）。GPT-4 一次通过率 55%，Claude 60%，GPT-5.6 是 74%。差距主要在复杂 DP 上，简单题三者差不多。
但 Claude 有个优势：代码注释更详细，变量命名也更语义化。GPT-5.6 的代码偏简洁，有时候读起来像竞赛选手写的——短但是需要脑补。GPT-4 居中，各方面比较均衡。
推理速度方面，GPT-5.6 比 GPT-4 快了大概 40%。我跑完 47 道题加修正，总共花了不到 20 分钟，同样的量 GPT-4 要半小时以上。这个对批量跑题来说挺重要的，毕竟谁也不想盯着进度条发呆。
实际能用在哪
测完这一轮，我的感受是 GPT-5.6 处理 DP 题已经能覆盖大部分面试和日常开发场景了。线性 DP 和背包类基本可以信任，复杂 DP 需要人工 review 和修正，但作为起点能省不少时间。
我现在刷题的习惯是这样的：先自己想 15 分钟，没思路就丢给 GPT-5.6 看它的分析过程，然后关掉自己写一遍。这个方法比我以前死磕一小时然后看题解效率高多了，因为它的推理过程是逐步展开的，能帮我理解"为什么要这么定义状态"——这个恰恰是 DP 最难的地方。
不过提醒一句：别直接拿它生成的代码去面试或者比赛。一是可能翻车，二是你没法解释清楚代码逻辑的话，面试官一眼就能看出来。我有个朋友今年年初面字节，用 ChatGPT 准备了几道 DP 题，结果面试官追问状态定义的动机，他直接卡住了。场面一度非常尴尬。
把它当学习工具和辅助工具用，别当替代品。
你们有没有用 GPT 或者 Claude 刷过算法题？哪类题 AI 处理得最好，哪类最拉胯？评论区聊聊，我后面打算再测一期图论相关的——最近在看 Tarjan 算法，感觉这东西丢给 AI 大概率要翻。有想看的题型可以告诉我。
#GPT5.6 #动态规划 #算法评测 #API测试 #LeetCode #AI编程
读者评论 5