背包、区间、树形和状态压缩 DP
概念解释
背包、区间、树形和状态压缩 DP是“贪心与动态规划”中的核心知识。区分局部选择可证明最优的问题与需要保存子问题状态的问题。
核心方法与条件
先识别问题对象、条件和目标，再把“背包、区间、树形和状态压缩 DP”与本章其他概念建立联系。写 DP 时依次说明状态含义、转移来源、初值、遍历顺序和答案位置。
例题或应用
写 DP 时依次说明状态含义、转移来源、初值、遍历顺序和答案位置。
常见易错点
只记住“背包、区间、树形和状态压缩 DP”的名称而不检查对象、条件、范围和证据，会导致机械套用。
自检
请尝试不用原文解释“背包、区间、树形和状态压缩 DP”解决什么问题，再设计一个属于“贪心与动态规划”的实例，并说明适用条件和判断依据。