一、什么是線性?

越是基礎的概念，越應該有一個透徹的理解，才能對上層問題有直接了當?shù)睦斫狻１热鐚€性分割器，你對線性有透徹的理解，一看這個名字就大概知道它是怎么回事了。

1. 幾何理解：線性關系就是直線關系

現(xiàn)在你可以想象一條曲線S，它可以是直的也可以是彎的，然后你得承認一個事實：曲線S上的任意一點，都可以由曲線S 上其他的任意一點沿著曲線移動而來。

然后我們來看這個移動。在二維坐標平面，移動就意味著橫坐標軸和縱坐標軸的變化，如果兩者的變化成一個倍數(shù)關系，即橫坐標變化了2，縱坐標就變化了6；而橫坐標變化了8，縱坐標就變化了24（當然這個倍數(shù)也可以是無窮，這時候?qū)@水平或豎直線）；像這種移動，則是在一條直線上的移動，否則，就是曲線上的移動。

都是移動，為啥直線移動比較特別呢？因為這種移動，不同坐標在放縮和疊加上保持一致，擴大而說就是 不同維度在放縮和疊加上保持一致。

好了到這里就可以回到最初的問題了，什么是線性？就是沿直線走的特性?。。?/p>

如何理解 “沿直線走的特性” ”不同維度的放縮和疊加保持一致“ ?

比如，一個線性信號處理系統(tǒng)，我們都知道它的定義就是：信號經(jīng)過疊加后經(jīng)過系統(tǒng)和經(jīng)過系統(tǒng)后在疊加是等價的，那么這個系統(tǒng)就是線性系統(tǒng)。

這按照 沿直線走的特性 來理解的話，就是這個系統(tǒng)是走直線的，就是輸入和輸出是走直線的，即輸入和輸出放縮和疊加上保持一致。輸入擴大了n倍，那么輸出也會擴大n倍，輸入是兩個信號的疊加，那么輸出也會是兩個相應輸出信號的疊加。

2. 數(shù)值理解：線性就是只進行放縮和疊加

為什么只進行放縮和疊加就是線性呢？因為直線的坐標進行只進行放縮和疊加的話，不同坐標是保持一致性的。

再比如，n維線性空間，為啥加線性空間呀？線性二字體現(xiàn)在哪里呢？三個基向量(1, 1, 0, 0)、(0, 1, 1, 0)、(0, 0, 1, 1) span的空間為一個三維線性空間，這時候這個空間的坐標單位就是上面三個向量，而一個向量它又是由四個數(shù)組成，線性就體現(xiàn)在這四個數(shù)中相應位置的數(shù)只進行了放縮和疊加，沒錯，線性就體現(xiàn)在這里。

二、什么是線性DP?

在線性結(jié)構(gòu)上進行狀態(tài)轉(zhuǎn)移，目標函數(shù)為特定變量的線性函數(shù)，目的是求目標函數(shù)的最大值或最小值。

1. 線性DP定義：

這里的定義只是一個概述，所謂的線性DP是指我們的遞推方程是存在一個線性的遞推關系?？梢允且痪S線性的、二維線性的、三維線性的、…。

最長上升子序列模型屬于線性DP。

2. DP解題套路

（1）把問題分解成若干子問題；

（2）根據(jù)題意列出狀態(tài)轉(zhuǎn)移方程；

（3）找出邊界；

（4）遞推求解。

DP問題核心就是枚舉，枚舉出問題所有可能的情況，然后取最優(yōu)解。DP算法實際上就是設計一種思路（狀態(tài)轉(zhuǎn)移方程），讓程序能高效率地運行出所求結(jié)果。