具有线性“阶段”划分的动态规划算法被统称为线性DP。
如果一个动态规划的状态包含多个维度，但是在每一个维度上都具有线性变化的阶段，那么该动态规划算法称为线性DP。经典的问题有：最长上升子序列(LIS)，最长公共子序列(LCS)，数字三角形等。
⚪数字三角形
问题描述：给定一个共有N行的三角矩阵A,其中第i行有i列。从左上角出发，每次可以向下方或右下方走一步，最终到达底部，求把经过的所有位置上的数加起来，和最大是多少。
状态表示：f[i,j]表示从左上角走到第i行第j列，和最大是多少
阶段划分：路径的结尾位置(矩阵中的行、列位置，即一个二维坐标)
转移方程：f[i,j]=A[i,j]+max(f[i-1,j], f[i-1,j-1](if j>1) )
边界：f[1,1]= A[1,1]
目标：max(f[N,j]) (1≤j≤N)
⚪最长上升子序列
问题描述：给定一个长度为的数列A，求数值单调递增的子序列的长度最长是多少。A的任意子序列B可表示为 B= {Ak1,Ak2,…,Akp },其中 k1<k2<…<kp。
状态表示：f[i]表示以 A[i]为结尾的“最长上升子序列”的长度
阶段划分：子序列的结尾位置(数列A中的位置，从前到后)
转移方程：f[i]=max(f[j]+1) (0≤j<i, A[j]<A[i])
边界：f[0]= 0
目标：max(f[i]) (1≤i≤N)
⚪最长公共子序列
问题描述：给定两个长度分别为N和M的字符串A和B，求既是A的子序列又是B的子序列的字符串的最长长度。
状态表示：F[i,j]表示前缀子串 A[1~i]与 B[1~j]的“最长公共子序列”的长度
阶段划分：已处理的前缀长度(两个字符串中的位置，即一个二维坐标)
转移方程：
f[i][j]=f[i−1][j−1]+1 (Ai==Bj);
f[i][j]=max(f[i−1][j],f[i][j−1]) (Ai≠Bj);
边界：f[i][0]=f[0][j]=0
目标：f[N][M]
容易发现，状态表示无论是一维还是多维，DP算法在这些问题上都体现为“作用在线性空间上的递推”—-DP的阶段沿着各个维度线性增长，从一个或多个边界点开始有方向地向整个状态空间转移、扩展，最后每个状态上都保留了以自身为“目标”的子问题的最优解。
在这类问题中，需要计算的对象表现出明显的维度以及有序性，每个状态的求解都直接构成一个阶段，这使得DP的状态表示就是阶段的表示。因此，我们只需要在每个维度上各取一个坐标值作为DP的状态，自然就可以描绘出“已求解部分”在状态空间中的轮廓特征，该轮廓的进展就是阶段的推移。另外，每个状态的求解显然只与之前阶段的最优解有关，最优子结构性质也得以验证。接下来，按顺序依次循环每个维度，根据问题要求递推求解的具体实现过程也就顺理成章了。
分类