DP问题分析方法
DP问题分析 —— yxc 的 DP问题分析方法
DP 的两个角度 状态表示 及 状态计算（状态转移方程）
化零为整：将具有共性的方案划归到一个集合中表示
化整为零：将集合进行划分成若干子集来分别求解
状态表示
很难根据题目现推，经验之谈居多
状态表示主要是两个角度 分别为 集合 和 属性
集合
根据题目来确定用几维空间来储存状态的集合，集合一般为满足多重条件下的方案的集合
选择问题（背包问题等）一般具有以下特性：
- 第一维的
i是只考虑前i个物品 - 剩下的维数为题目的几个限制，例如重量、数量、体积等
属性
属性一般是给集合表示的方案进行值的定性，一般为 最大值、最小值、数量 等
状态计算
状态计算一般为对集合进行一个划分，划分为若干个子集
一般是通过方案最后的一个不同点来进行划分
（例如 01背包问题 中通过选或者不选择第 i 个物品将集合划分为两个子集）
划分出的子集有两个原则 不重复 与 不遗漏
常见的模型
组合模型
假设有一堆物品，在满足某种限制的条件下挑一些物品出来（部分选择合法），求所有组合中最好的情况
常见背包问题