DSA MASTERY · CURRICULUM

Ch.14

动态规划

围绕状态、转移、边界和计算顺序建立动态规划方法。

draft · 草稿

学习目标

从暴力搜索中识别重叠子问题，并写出精确的状态语义
在记忆化搜索、自底向上递推和空间压缩之间双向翻译
根据依赖方向完成线性、网格与背包动态规划建模
用正确性证明、复杂度分析和最小反例验证状态设计

从状态合同到可验证的转移

14.1 状态、决策、无后效性与答案位置
14.2 递归参数、缓存维度、拓扑顺序与方案还原
14.3 线性/网格依赖、滚动数组与附加状态
14.4 0-1/完全背包、组合/排列与循环方向

已有内容入口

第 14 章动态规划：把重复搜索折叠成状态章节导读 14.1 动态规划思维与状态设计理论文章 14.2 从记忆化搜索到递推理论文章 14.3 线性与网格动态规划理论文章 14.4 背包动态规划：选择次数、目标语义与循环顺序理论文章 Lab 14-E-01：爬楼梯相关 Lab Lab 14-E-02：最小花费爬楼梯相关 Lab Lab 14-E-03：数字三角形相关 Lab Lab 14-E-04：最大子段和相关 Lab Lab 14-E-05：打家劫舍相关 Lab Lab 14-E-06：滑雪相关 Lab Lab 14-E-07：挖地雷相关 Lab Lab 14-E-08：矩阵中的最长递增路径相关 Lab Lab 14-E-09：最长上升子序列相关 Lab Lab 14-E-10：合唱队形相关 Lab Lab 14-E-11：尼克的任务相关 Lab Lab 14-E-12：不同路径相关 Lab Lab 14-E-13：过河卒相关 Lab Lab 14-E-14：不同路径 II相关 Lab Lab 14-E-15：最小路径和相关 Lab Lab 14-E-16：传纸条相关 Lab Lab 14-E-17：编辑距离相关 Lab Lab 14-E-18：采药相关 Lab Lab 14-E-19：装箱问题相关 Lab Lab 14-E-20：疯狂的采药相关 Lab Lab 14-E-21：小 A 点菜相关 Lab Lab 14-E-22：分割等和子集相关 Lab Lab 14-E-23：零钱兑换相关 Lab Lab 14-E-24：零钱兑换 II相关 Lab Lab 14-E-25：组合总和 IV相关 Lab Lab 14-E-26：宝物筛选相关 Lab Lab 14-E-27：通天之分组背包相关 Lab Lab 14-E-28：樱花相关 Lab Lab 14-E-29：金明的预算方案相关 Lab Lab 14-E-30：Buying Hay相关 Lab