第9章笔记：动态规划基础模型

目标

把问题压成最小充分状态，写清转移来源、顺序与初始化。

七课依赖

• DP状态与DAG视角：围绕DP状态与DAG视角先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：状态必须无后效；零一背包倒序、完全背包正序不能混用。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 线性DP与最大子段和：围绕线性DP与最大子段和先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：状态必须无后效；零一背包倒序、完全背包正序不能混用。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 最长递增子序列：围绕最长递增子序列先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：状态必须无后效；零一背包倒序、完全背包正序不能混用。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 零一背包：围绕零一背包先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：状态必须无后效；零一背包倒序、完全背包正序不能混用。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 完全与多重背包：围绕完全与多重背包先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：状态必须无后效；零一背包倒序、完全背包正序不能混用。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 路径与计数DP：围绕路径与计数DP先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：状态必须无后效；零一背包倒序、完全背包正序不能混用。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 方案恢复与滚动数组：围绕方案恢复与滚动数组先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：状态必须无后效；零一背包倒序、完全背包正序不能混用。 本课必须再检查边界输入、整数溢出、下标和不可行状态。

复杂度与适用条件表

算法对象	不变量/复杂度来源	使用边界
DP状态与DAG视角	围绕DP状态与DAG视角先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	状态必须无后效；零一背包倒序、完全背包正序不能混用。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
线性DP与最大子段和	围绕线性DP与最大子段和先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	状态必须无后效；零一背包倒序、完全背包正序不能混用。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
最长递增子序列	围绕最长递增子序列先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	状态必须无后效；零一背包倒序、完全背包正序不能混用。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
零一背包	围绕零一背包先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	状态必须无后效；零一背包倒序、完全背包正序不能混用。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
完全与多重背包	围绕完全与多重背包先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	状态必须无后效；零一背包倒序、完全背包正序不能混用。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
路径与计数DP	围绕路径与计数DP先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	状态必须无后效；零一背包倒序、完全背包正序不能混用。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
方案恢复与滚动数组	围绕方案恢复与滚动数组先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	状态必须无后效；零一背包倒序、完全背包正序不能混用。 本课必须再检查边界输入、整数溢出、下标和不可行状态。

复盘

每题保存暴力、优化、证明、四组边界测试和首个WA输入；一周后换数据重做。