线性动态规划
介绍
线性动态规划的主要特点是状态的推导是按照问题规模i从小到大依次推过去的，较大规模的问题的解依赖较小规模的问题的解。
这里问题规模为i的含义是考虑前i个元素[0..i]时问题的解。
状态定义:
dp[n] := [0..n] 上问题的解
状态转移:
dp[n] = f(dp[n-1], ..., dp[0])
从以上状态定义和状态转移可以看出，大规模问题的状态只与较小规模的问题有关，而问题规模完全用一个变量i表示i的大小表示了问题规模的大小，因此从小到大推i直至推到n，就得到了大规模问题的解，这就是线性动态规划的过程。
主要解决的问题
单串
单串dp[i] 线性动态规划最简单的一类问题，输入是一个串，状态一般定义为 dp[i] := 考虑[0..i]上，原问题的解，其中i位置的处理，根据不同的问题，主要有两种方式：
- 第一种是
i位置必须取，此时状态可以进一步描述为dp[i] := 考虑[0..i]上，且取 i，原问题的解； - 第二种是
i位置可以取可以不取
线性动态规划中单串 dp[i] 的问题，状态的推导方向以及推导公式如下：
- 依赖比 i 小的 O(1) 个子问题
dp[n]只与常数个小规模子问题有关，状态的推导过程dp[i] = f(dp[i - 1], dp[i - 2], ...)。时间复杂度 O(n)，空间复杂度 O(n) 可以优化为 O(1)
- 依赖比 i 小的 O(n) 个子问题
dp[n]与此前的更小规模的所有子问题dp[n - 1], dp[n - 2], ..., dp[1] 都可能有关系。
状态推导过程为：dp[i] = f(dp[i - 1], dp[i - 2], ..., dp[0])
双串
线性动态规划中双串dp[i][j]的问题，状态的推导方向以及推导公式如下:
如图所示，绿色部分的dp[i-1 ~ 0][j-1 ~ 0]均已经计算过，但计算橙色的当前状态时，仅用到dp[i-1][j], dp[i][j-1], dp[i-1][j-1]，即比 i, j 小的O(1)个子问题。