前言：最近做了很多动态规划题，但是每次遇到新的题目的时候还是做不出来，于是就像做一个小结，梳理下近些天做的题目，从中获取经验。
第零节：DP的基础概念
动态规划和其他某些算法具有一定的相似度，都是利用问题的可划分性以及子问题的相似性来进行归纳，降低时间复杂度。
来说说动态规划的几个基本条件：
| 条件 | 解释 |
|---|---|
| 无后效性 | 已求解的子问题不受后续阶段的影响$^{[1]}$ |
| 最优子结构 | 下一个阶段的最优解应该能够由前面各阶段子问题的最优解导出 |
| 子问题重叠 | 动态规划通过对每个子问题只解一次，把解保存在一个需要时就可以查看的表中$^{[2]}$ |
[1]：在《算法竞赛进阶指南》中有一个很好的说法，“动态规划对状态空间的遍历构成一张有向无环图，遍历顺序就是该图的一个拓扑序。”
[2]：其实就是动态规划会用查询的方式解决重复出现的子问题，而不是像递归那样每次算一遍。
构成动态规划的三要素：
| 要素 | 解释 |
|---|---|
| 状态 | 即我们通常所说的f或dp数组，他们用来表示什么 |
| 阶段 | 即各个状态在不同时刻的表示 |
| 决策 | 状态如何转移到 下一个状态 |
知道了这些并没有什么用，重要的还是在题目中体会。
第一节：线性DP
我们在解决一些线性区间上的最优化问题的时候，往往也能够利用到动态规划的思想，这种问题可以叫做线性dp。
- 线性空间
在有关线性dp问题中，有着几个比较经典而基础的模型，例如最长上升子序列(LIS)、最长公共子序列(LCS)、最大子序列和等，那么首先我们从这几个经典的问题出发开始对线性dp的探索。
注：下表引用自《算法竞赛进阶指南》P258表
| 问题描述 | 最长上升子序列。给定一个长度为$N$的数列$A$，求数值单调递增的子序列的长度是多少。$A$的任意子序列$B$可表示为$B={A_{k1},A_{k2},…,A_{kp}}$，其中$k_1<k_2<…<k_p$ |
| 状态表示 | $F[i]$表示以$A[i]$为结尾的“最长上升子序列”的长度 |
| 阶段划分 | 子序列的位置（数列$A$中的位置，从前到后） |
| 转移方程 | $F[i]=max{F[j]+1},0\le j<i,A[j]<A[i]$ |
| 边界 | $F[0]=0$ |
| 目标 | $max{F[i]},1\le i \le N$ |
还有两个大家自行看书~（打这个太累啦）
通过这三个问题，我们可以了解到，线性DP无论是多维还是一维，“线性”都体现在“作用在空间上的递推”————DP的阶段沿着各个维度线性增长，从一个或多个“边界点”开始有方向地向整个状态空间转移、扩展，最后每个状态上都保留了以自身为目标子问题的最优解。
下面我们开始线性DP的进阶，我们从例题开始。
【例1】Mr. Young’s Picture Permutations$^{poj2279}$
这是一个五维的线性DP，从该题给出的解法中我们发现，设计动态规划的状态转移方程，不一定要以“如何计算出一个状态”的形式给出，也可以考虑“一个已知状态应该更新哪些后续阶段的未知状态”。
第二节：背包
其实我们OIer很多时候都是靠眼睛学习的，偶尔通过听觉也是不错的。
⭐0/1背包
⭐完全背包
⭐多重背包
⭐分组背包
区间DP
树形DP
⭐背包类树形DP
推荐个视频