第10章笔记：区间、树形与状态压缩DP

目标

在更复杂依赖图上组织区间长度、子树后序和子集枚举。

七课依赖

• 区间DP的枚举顺序：围绕区间DP的枚举顺序先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：状态压缩只适合小维度；区间DP必须保证子区间已计算。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 石子合并：围绕石子合并先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：状态压缩只适合小维度；区间DP必须保证子区间已计算。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 括号与回文区间：围绕括号与回文区间先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：状态压缩只适合小维度；区间DP必须保证子区间已计算。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 树形DP与换根：围绕树形DP与换根先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：状态压缩只适合小维度；区间DP必须保证子区间已计算。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 子集枚举技巧：围绕子集枚举技巧先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：状态压缩只适合小维度；区间DP必须保证子区间已计算。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 旅行商状态压缩：围绕旅行商状态压缩先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：状态压缩只适合小维度；区间DP必须保证子区间已计算。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 数位DP入口：围绕数位DP入口先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：状态压缩只适合小维度；区间DP必须保证子区间已计算。 本课必须再检查边界输入、整数溢出、下标和不可行状态。

复杂度与适用条件表

算法对象	不变量/复杂度来源	使用边界
区间DP的枚举顺序	围绕区间DP的枚举顺序先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	状态压缩只适合小维度；区间DP必须保证子区间已计算。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
石子合并	围绕石子合并先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	状态压缩只适合小维度；区间DP必须保证子区间已计算。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
括号与回文区间	围绕括号与回文区间先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	状态压缩只适合小维度；区间DP必须保证子区间已计算。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
树形DP与换根	围绕树形DP与换根先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	状态压缩只适合小维度；区间DP必须保证子区间已计算。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
子集枚举技巧	围绕子集枚举技巧先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	状态压缩只适合小维度；区间DP必须保证子区间已计算。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
旅行商状态压缩	围绕旅行商状态压缩先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	状态压缩只适合小维度；区间DP必须保证子区间已计算。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
数位DP入口	围绕数位DP入口先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	状态压缩只适合小维度；区间DP必须保证子区间已计算。 本课必须再检查边界输入、整数溢出、下标和不可行状态。

复盘

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