动态规划并不是黑魔法
动态规划被描述为一种系统性方法：通过识别重叠子问题并缓存结果，把指数时间的递归问题转化为高效算法。评论者围绕如何最好地理解和教授它展开讨论——自顶向下的递归加记忆化，还是自底向上的填表——并指出记忆化、优化及相关术语经常被混用或解释不清。帖子还涉及这一技术的起源与命名、它与 Dijkstra 等算法的关系，以及 DP 在实践中的真实出现场景，从面试题到生物信息学和组合计数。
定义与概念框架
- DP 被描述为一种用于解决多阶段或离散时间决策/优化问题的方法：定义一个价值函数，使每个状态的值取决于“更小”状态的最优值。
- 多位评论者强调，“最优子结构”和重叠子问题才是真正核心，而不是代码层面的技巧。
- 也有人将其简化为：递归 + 记忆化 +（良好）的问题分解，并指出最难的部分是找到正确的递推关系。
记忆化 vs 动态规划
- 常见问题：“DP 就只是记忆化吗？”
- 一方认为：记忆化是一种通用缓存技术；DP 是在结构化的子问题空间上的系统性记忆化，通常可用 DAG 解释并按自底向上的顺序处理。
- 另一些人则认为，实践中 DP 问题可以被教和实现为“先递归，再加记忆化（自顶向下），然后转成自底向上的表格法并优化空间”。
- 斐波那契、编辑距离、LCS、背包、子集和以及股票交易问题等例子被用来说明自顶向下与自底向下的差异，以及何时可以把表缩减为几行或常数级空间。
教学与难度
- 许多人觉得 DP 经常教得不好：直接跳到表格会让它看起来像谜题或“黑魔法”。
- 倡导的教学模式：
- 先得到一个正确的（可能是指数时间的）递归解；
- 加上记忆化；
- 将其转成迭代/表格化解法；
- 如可能，再优化内存。
- 对最佳心智模型存在分歧：“聪明缓存” vs 更抽象的“子问题 DAG / 动态优化”。一方更重可理解性，另一方更重概念严谨性。
提到的算法与应用
- 经典 DP 问题：最长公共子序列/子串、自动换行、硬币找零、背包、子集和、矩阵链乘、编辑距离、DAG 上最长路径、路径上的加权独立集、DAG 上最短路、序列比对（Needleman–Wunsch、Smith–Waterman）。
- 现实/遗留用途：围棋局面计数、生物信息学、Emacs 屏幕重绘、谜题/关卡生成、Advent of Code 题解。
- 关于 Dijkstra 算法是否应归类为 DP 的争论；有人认为可以，因为它满足动态规划的最优性条件并可用标签修正视角理解，另一些人则认为它的状态探索方式不同于标准 DP 表格法。
命名、历史与认知
- 多条评论回顾了历史起源：“programming” 指的是优化意义上的“编程”；“dynamic” 则因政治/营销原因而选用。
- 有人抱怨这个术语具有误导性或过于宽泛；也有人建议使用更具描述性的名称，如“表格法（tabulation）”或“数组记忆化（array memoization）”。
实践中的使用与面试
- 对实际使用的反馈不一：有人在竞赛/AoC 之外几乎不需要 DP；也有人指出它悄然支撑着许多库算法，并有助于避免意外的二次复杂度。
- 强烈观点认为在面试中应接受其他正确方法（例如遗传算法），但也有人反驳说，随机化/启发式方法与具有明确时间界限的确定性 DP 在本质上不同。
其他讨论线索
- 关于什么算科学的简短元讨论（顺带提到精神分析），以及“optimization”和“bootstrap”等概念是如何命名与被感知的。