线性动态规划是具有线性阶段划分的动态规划算法，也称线性DP。若状态包含多个维度，则每个维度都是线性划分的阶段，也属于线性DP，如下图所示：
线性动态规划-01.png
序列问题
- 最长上升子序列 剑指 Offer II 095. 最长公共子序列
Longest Increasing Subsequence问题，最长上升子序列，其一般为求序列A最长上升或下降子序列。
求解过程：dp[i]表示以A序列i为结尾的最长上升子序列的长度，则有转移方程为：
- 最长公共子序列 剑指 Offer II 095. 最长公共子序列
Longest Common Subsequence问题，最长公共子序列，求取两个序列A和B的最长公共子序列。
求解过程：dp[i,j]表示子串A[1,...,i]与B[1,...,j]的最长公共子序列的长度，转移方程为：
字符串编辑距离
- 字符串编辑距离 72. 编辑距离
Levenshtein问题，字符串编辑距离，求取从字符串A到字符串B的编辑单个字符所需的最少次数，其中编辑单个字符可以有删除、替换、插入。
求解过程：dp[i,j]表示字符串A的前个位置到字符串
B的前个位置的编辑距离，转移方程为：
最大和问题
- 最大子序列和 53. 最大子数组和
最大子序列和问题，对给定序列a[1],a[2],a[3],...,a[n]寻找它的连续的最大和子数组。
求解过程：dp[i]表示保存前最大的连续子数组，转移方程为：
- 最大子矩阵和 面试题 17.24. 最大子矩阵
最大子矩阵和问题，给定一个n行m列的整数矩阵a，现在要求a的一个子矩阵，使其各元素之和为最大。
求解过程：由于最终的子矩阵一定在某两行之间，所以可以先对数据进行处理降低时间复杂度，即。这样的话，最大子矩阵的搜索问题就转移到了当两行确定是去算两行
i和j之间的最大值dp[k]，转移方程为：
数字三角形问题，给定一个如下形式的数字三角形a，现在要从左上角走到最底层，每一步只能走到相邻的结点，求经过的结点的最大数字和/最小数字和。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
求解过程：dp[i,j]表示走到第i行第j列的最大/最小和，转移方程为：
