什么是线性DP?

一、什么是线性?

越是基础的概念，越应该有一个透彻的理解，才能对上层问题有直接了当的理解。比如对线性分割器，你对线性有透彻的理解，一看这个名字就大概知道它是怎么回事了。

1. 几何理解：线性关系就是直线关系

现在你可以想象一条曲线S，它可以是直的也可以是弯的，然后你得承认一个事实：曲线S上的任意一点，都可以由曲线S 上其他的任意一点沿着曲线移动而来。

然后我们来看这个移动。在二维坐标平面，移动就意味着横坐标轴和纵坐标轴的变化，如果两者的变化成一个倍数关系，即横坐标变化了2，纵坐标就变化了6；而横坐标变化了8，纵坐标就变化了24（当然这个倍数也可以是无穷，这时候对应这水平或竖直线）；像这种移动，则是在一条直线上的移动，否则，就是曲线上的移动。

都是移动，为啥直线移动比较特别呢？因为这种移动，不同坐标在放缩和叠加上保持一致，扩大而说就是 不同维度在放缩和叠加上保持一致。

好了到这里就可以回到最初的问题了，什么是线性？就是沿直线走的特性！！！

如何理解 “沿直线走的特性” ”不同维度的放缩和叠加保持一致“ ?

比如，一个线性信号处理系统，我们都知道它的定义就是：信号经过叠加后经过系统和经过系统后在叠加是等价的，那么这个系统就是线性系统。

这按照 沿直线走的特性 来理解的话，就是这个系统是走直线的，就是输入和输出是走直线的，即输入和输出放缩和叠加上保持一致。输入扩大了n倍，那么输出也会扩大n倍，输入是两个信号的叠加，那么输出也会是两个相应输出信号的叠加。

2. 数值理解：线性就是只进行放缩和叠加

为什么只进行放缩和叠加就是线性呢？因为直线的坐标进行只进行放缩和叠加的话，不同坐标是保持一致性的。

再比如，n维线性空间，为啥加线性空间呀？线性二字体现在哪里呢？三个基向量(1, 1, 0, 0)、(0, 1, 1, 0)、(0, 0, 1, 1) span的空间为一个三维线性空间，这时候这个空间的坐标单位就是上面三个向量，而一个向量它又是由四个数组成，线性就体现在这四个数中相应位置的数只进行了放缩和叠加，没错，线性就体现在这里。

二、什么是线性DP?

在线性结构上进行状态转移，目标函数为特定变量的线性函数，目的是求目标函数的最大值或最小值。

1. 线性DP定义：

这里的定义只是一个概述，所谓的线性DP是指我们的递推方程是存在一个线性的递推关系。可以是一维线性的、二维线性的、三维线性的、…。

最长上升子序列模型属于线性DP。

2. DP解题套路

（1）把问题分解成若干子问题；

（2）根据题意列出状态转移方程；

（3）找出边界；

（4）递推求解。

DP问题核心就是枚举，枚举出问题所有可能的情况，然后取最优解。DP算法实际上就是设计一种思路（状态转移方程），让程序能高效率地运行出所求结果。