1.问题意识->抓主要矛盾
2.Dp（1）状态（I）阶段 （II）可求（III）可转移（2）转移
3.Dp优化（1）复杂度 状态*转移->区分空间复杂度&状态复杂度
（2）优化 （I）利用状态间的关系（II）预处理前后无关的转移
2026.2.8课堂总结
一，DP相关
1.DP必备条件：
（1）最优子结构：即由A状态的最优解可推到B状态的最优解
若不满足，Solve：（I） 重设状态（II）讨论不满足情况的性质
（2）重叠子问题：即某层状态可被分为性质相似，结构几乎相同的子问题
2.（求最优解）DP可看作以状态为点，转移为边的图并在其上求最短路
3.有环DP可使用SPFA求解，相对于Dijkstra，优点在无需建图，可以直接松弛
4.状态：I类：转移，可求，阶段；II类：重叠子问题
5.后效性：定义：不在状态中的信息对后面产生效用
DP要求无后效性，
若有后效性 Solve：（1）重设状态（2）细分方案，扩充状态（3）费用提前计算
二，从答案出发考虑问题
1.从答案的形式出发
（1）考虑最后形式（由过程推的），进行求解（大概率与过程无关）
（2）考虑最后一步进行前的形式
2.对答案进行调整：先构造满足一部分条件的答案，再依据其他条件对答案进行调整
三，从限制的角度考虑问题
1.去掉限制：即通过某种算法去除限制
2.满足限制：即构造答案满足所有限制
3.限制的存在：某些限制其实并不成立，可以不做考虑
