线性动态规划

线性动态规划的主要特点是状态的推导是按照问题规模 i 从小到大依次推过去的，较大规模的问题的解依赖较小规模的问题的解。这里问题规模为 i 的含义是考虑前 i 个元素[0..i]时问题的解。

状态定义：
dp[n] := [0..n] 上问题的解
状态转移：
dp[n] = f(dp[n-1], ..., dp[0])

从线性动态规划的状态中可以看出，大规模问题的状态只与较小规模的问题有关，而问题规模完全用一个变量 i 表示，i 的大小表示了问题规模的大小，因此从小到大推 i 直至推到 n，就得到了大规模问题的解，这就是线性动态规划的过程。

线性动态规划解决的问题主要是单串，双串，矩阵上的问题。

具体例题有：最大子数组和、最长上升子序列（参见我的博客）、粉刷房子（带维度单串dp[i][k]）

区间动态规划

区间 DP 是状态的定义和转移都与区间有关，其中区间用两个端点表示。

状态定义 dp[i][j] 代表在区间 [i..j] 上原问题的解。推导状态的过程一般按照区间长度从短到长逐渐求得。

以单串为例，对于 dp[i][j] ，原问题的解增加 i，减小 j 都可以得到更小规模的子问题。

具体例题有：最长回文子序列（这个题的转移方程很巧妙，需要多看看，参见力扣官方题解）

实际应用中的动态规划

Bellman-Ford算法：处理存在负权边的单源最短路问题的算法，效率不高，但是可以判断是否存在负权环
强化学习（相关内容：马尔科夫决策过程-MDP）

注：本文参考自课程ppt