谓线性DP，就是递推方程是有一个明显的线性关系的，一维线性和二维线性甚至多维都有可能。
动态规划里的每一个状态都是一个多维(1-n维)的状态。
比如说背包问题就是一个二维的问题，如果我们把它画出来的话会是一个二维矩阵的形式。
而我们在求的时候，有一个明显的求的顺序：即一行一行地来求。这样的有线性顺序的叫做线性DP
线性dp，是较常见的一类动态规划问题，其是在线性结构上进行状态转移，这类问题不像背包问题、区间DP等有固定的模板。
线性动态规划的目标函数为特定变量的线性函数，约束是这些变量的线性不等式或等式，目的是求目标函数的最大值或最小值。
因此，除了少量问题（如：LIS、LCS、LCIS等）有固定的模板外，大部分都要根据实际问题来推导得出答案。

原文链接：https://blog.csdn.net/George54276/article/details/126880701