线性 DP
笔者认为，DP 也是一种思想，是一种以空间换时间的思想。
DP 一般存在三种实现方式：
- 记忆化搜索
- 拓扑排序
- 扫表
三种实现方式各有一定的优劣，将在后文中分析。
DP 从形式上分为三部分：
- 状态
- 状态转移
- 初始化
其中实现状态转移的式子常被称为状态转移方程。
而转移的方式，也在部分场景下被细分为“顺推”和“逆推”。
“顺推”为用当前状态去更新可以转移到的状态，为“到哪去”。
“逆推”为用可以转移到的状态来更新当前状态，为“从哪来”。
“顺推”和“逆推”在部分情况下有优劣，但一般无影响，将在后文考虑。
DP 转移时需要保证用来转移的状态是已经正确的。
DP 的时间复杂度为 $O(状态数\times 转移时间)$。
本文将介绍若干 DP 入门例题帮助 DP 思维的建立。
线性 DP 是指在线性结构上进行转移。在实际问题中，一般在序列上和矩阵上考虑较多。
矩阵 DP：
$[IOI1994]$ 第一次在算法竞赛引入了动态规划的思想。
例 $1$：
给定一个 $n$ 层的数字三角形每次可以从 $(x,y)$ 走到 $(x+1,y),(x+1,y+1)$，求从 $(1,1)$ 出发经过路径上数字之和的最大值。
状态：
设 dp$[x][y]$ 为从起点到 $(x,y)$ 的答案。
状态转移：
$(x,y)\rightarrow(x+1,y),(x+1,y+1)$
$(x,y)\leftarrow(x-1,y),(x-1,y-1)$
所以写出 DP 式子：
- 顺推：
dp[x+1][y]=max(dp[x][y]+a[x+1][y],dp[x+1][y]),dp[x+1][y+1]=max(dp[x][y]+a[x+1][y+1],dp[x+1][y+1]) - 逆推：
dp[x][y]=max(dp[x-1][y],dp[x-1][y-1])+a[x][y]
在一般的 DP 问题中，普遍采用扫表的方式实现 DP。扫表即使用循环枚举状态，所以对于扫表法来说，枚举的顺序很重要。
此题中因为每一层的状态一定是在相邻的两层之间转移，所以按层枚举，而层内的顺序则不影响。
初始化：
从 $(1,1)$ 开始，所以可以将 $(1,1)$ 设为初始状态，初始化 dp$[1][1]=a[1][1]$，后从第二层开始枚举。同时因为求的是极大值，所以要将 dp 数组初始化为极小值。
最后的解即为 dp$[n][n]$。
时间复杂度：$O(n^2)$。
空间复杂度：$O(n^2)$。
DP 空间换时间，所以空间复杂度普遍偏高，内存超限也多出现在 DP 问题中。
序列 DP：
例 2：
给定一个长度为 $n$ 的序列 $a_i$，求最长上升子序列。
状态：
设 dp$[i]$ 为以 $a_i$ 结尾的最长上升子序列长度。
状态转移：
$(i)\rightarrow (j)(a_j>a_i)$
$(i)\leftarrow(j)(a_j<a_i)$
这里一个小区别就是转移的状态不确定了，不是固定的。
所以需要去枚举转移：
- 顺推：
For(j,i+1,n) if(a[j]>a[i]) dp[j]=max(dp[j],dp[i]+1) - 逆推：
For(j,1,i-1) if(a[j]<a[i]) dp[i]=max(dp[i],dp[j]+1)
初始化：
每一个位置本身可以是最长上升子序列的开始，所以可以将 $(1),…,(n)$ 都初始化为 $1$ 以作为初始状态。
在序列上，每一个位置的答案一定是由它之前的转移过来，所以按顺序枚举即可。
最后的解即为：dp$[n]$。
时间复杂度：$O(n^2)$。
空间复杂度：$O(n)$。
事实上，此处的 DP 转移可以优化做到 $O(n\log n)$ 的时间复杂度，将在之后的文章提到。
总结以上两个例子，矩阵中进行 DP，往往设 dp$[x][y]$ 表示从起点到 (x,y) 的答案；序列中进行 DP，往往设 dp$[x]$ 表示从 $1$ 到 $x$ 的答案。在具体的题目中，也会有相应的扩展。
扩展：
DP 和 贪心：
DP 和贪心都是一种思想，它们之间没有明确的界限。可以说贪心是一种特殊的 DP，也可以认为 DP 是一种特殊的贪心，自行理解即可。
考虑下面一个问题：
例 3：
求用面值 $1,3,5$ 分的硬币支付 $x$ 分钱的最少硬币数量。
考虑贪心：优先使用 $5$ 分，直到不能用 $5$ 分后再用 $3$ 分，最后用 $1$ 分。
证明：
引理：最后的硬币方案，一定最多 $1$ 个 $3$ 或者 $2$ 个 $1$。
反证。若存在 $2$ 个 $3$，则可以替换成 $1$ 个 $1$ 和 $1$ 个 $5$ 不会更劣。
若有 $3$ 个 $1$，则可能替换成 $1$ 个 $3$，更优。
也就是说用 $1$ 和 $3$ 只能支付小于 $5$ 的面额。而优先使用 $5$ 之后，剩下的只能是 $0,1,2,3,4$，分别考虑也可证明策略的正确性。
例 4：
求用面值 $2,4,5$ 分的硬币支付 $x$ 分钱的最少硬币数量，或判断无解。
此时，贪心显然错误。考虑 $x=6$ 时，贪心策略无解。
考虑 DP。
状态：
设 dp$[x]$ 表示支付 $x$ 分钱的最少硬币数量。
状态转移：
- $(x)\rightarrow (x+2),(x+4),(x+5)$
- $(x)\leftarrow(x-2),(x-4),(x-5)$
所以写出 DP 式子：
- 顺推：
dp[x+2]=max(dp[x+2],dp[x]+1),dp[x+4]=max(dp[x+4],dp[x]+1),dp[x+5]=max(dp[x+5],dp[x]+1) - 逆推：
dp[x]=max(dp[x-2],dp[x-4],dp[x-5])+1
初始化：
初始情况下没有任何硬币，所以应该选择 $(0)$ 作为初始状态并初始化 dp$[0]=0$。同时要注意无解的情况。所以要特殊处理无解，一般可以之间置为极大值（求解最小值）或者极小值（求解最大值）。
容易发现，大金额的状态是由小金额的状态转移的，所以从小到大枚举金额即可。
最后的解即为：dp$[x]$。
Tips：在后续的内容，为了避免不必要的内容，除非必要，将统一使用逆推。