具有「線性」階段劃分的動態規劃方法統稱為線性動態規劃（簡稱為「線性 DP」），如下圖所示。

一、概念

如果狀態包含多個維度，但是每個維度上都是線性劃分的階段，也屬于線性 DP。比如背包問題、區間 DP、數位 DP 等都屬于線性 DP。

線性 DP 問題的劃分方法有多種方式。

• 如果按照「狀態的維度數」進行分類，我們可以將線性 DP 問題分為：一維線性 DP 問題、二維線性 DP 問題，以及多維線性 DP 問題。
• 如果按照「問題的輸入格式」進行分類，我們可以將線性 DP 問題分為：單串線性 DP 問題、雙串線性 DP 問題、矩陣線性 DP 問題，以及無串線性 DP 問題。

二、單串線性 DP 問題

1. 問題

單串線性 DP 問題：問題的輸入為單個數組或單個字符串的線性 DP 問題。狀態一般可定義為 dp[i]，表示為：

1. 「以數組中第 i個位置元素 nums[i]] 為結尾的子數組（nums[0]...nums[i]）」的相關解。
2. 「以數組中第 i?1個位置元素 nums[i?1]為結尾的子數組（nums[0]...nums[i?1]）」的相關解。
3. 「以數組中前 i個元素為子數組（nums[0]...nums[i?1]）」的相關解

這 3 種狀態的定義區別在于相差一個元素 nums[i]。

1. 第 1種狀態：子數組的長度為 i+1，子數組長度不可為空；
2. 第 2 種狀態、第 3 種狀態：這兩種狀態描述是相同的。子數組的長度為 i，子數組長度可為空。在 i=0時，方便用于表示空數組（以數組中前 0 個元素為子數組）

三、最長遞增子序列

單串線性 DP 問題中最經典的問題就是「最長遞增子序列（Longest Increasing Subsequence，簡稱 LIS）」。

1. 實戰練習

給定一個整數數組 nums，找到其中最長嚴格遞增子序列的長度

• 子序列：由數組派生而來的序列，刪除（或不刪除）數組中的元素而不改變其余元素的順序。例如，[3,6,2,7] 是數組 [0,3,1,6,2,2,7] 的子序列。
• 1≤nums.length≤2500。
• ?10^4≤nums[i]≤10^4。

2. 代碼

class Solution {// 定義長度最長遞增子序列的方法lengthOfLIS(nums) {// 獲取數組的長度const size = nums.length;// 創建并初始化動態規劃數組，初始值為1const dp = new Array(size).fill(1);// 外層循環迭代每個元素for (let i = 0; i < size; i++) {// 內層循環迭代當前元素之前的元素for (let j = 0; j < i; j++) {// 如果當前元素大于之前的元素，可以將當前元素加入遞增子序列if (nums[i] > nums[j]) {// 更新以當前元素結尾的遞增子序列的長度dp[i] = Math.max(dp[i], dp[j] + 1);}}}// 返回動態規劃數組中的最大值，即為最長遞增子序列的長度return Math.max(...dp);}
}// 示例用法
const solution = new Solution();
// 輸出最長遞增子序列的長度
console.log(solution.lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]));

四、最大子數組和

單串線性 DP 問題中除了子序列相關的線性 DP 問題，還有子數組相關的線性 DP 問題。

注意：

• 子序列：由數組派生而來的序列，刪除（或不刪除）數組中的元素而不改變其余元素的順序。
• 子數組：指的是數組中的一個連續子序列。

「子序列」與「子數組」都可以看做是原數組的一部分，而且都不會改變原來數組中元素的相對順序。其區別在于數組元素是否要求連續。

1. 實戰練習

給定一個整數數組 nums，找到一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和

2. 代碼

class Solution {maxSubArray(nums) {// 獲取數組的長度const size = nums.length;// 創建并初始化動態規劃數組，初始值為0const dp = new Array(size).fill(0);// 初始化動態規劃數組的第一個元素dp[0] = nums[0];// 從數組的第二個元素開始遍歷for (let i = 1; i < size; i++) {// 如果前一個元素的動態規劃值小于0，說明不利于累積當前元素，直接以當前元素為起點重新計算if (dp[i - 1] < 0) {dp[i] = nums[i];} else {// 否則，累積當前元素，更新動態規劃值dp[i] = dp[i - 1] + nums[i];}}// 返回動態規劃數組中的最大值，即為最大子數組和return Math.max(...dp);}
}// 示例用法
const solution = new Solution();
// 輸出最大子數組和
console.log(solution.maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]));

五、最長的斐波那契子序列的長度

有一些單串線性 DP 問題在定義狀態時需要考慮兩個結束位置，只考慮一個結束位置的無法清楚描述問題。這時候我們就需要需要增加一個結束位置維度來定義狀態

1. 實戰練習

給定一個嚴格遞增的正整數數組 arr，從數組 arr 中找出最長的斐波那契式的子序列的長度。如果不存斐波那契式的子序列，則返回 0。

2. 代碼

class Solution {lenLongestFibSubseq(arr) {const size = arr.length;let ans = 0;// 枚舉所有可能的前兩個數for (let i = 0; i < size; i++) {for (let j = i + 1; j < size; j++) {let tempAns = 0;let tempI = i;let tempJ = j;let k = j + 1;// 在數組中搜索斐波那契子序列while (k < size) {// 如果當前三個數滿足斐波那契關系if (arr[tempI] + arr[tempJ] === arr[k]) {tempAns += 1;tempI = tempJ;tempJ = k;}k += 1;}// 更新最大斐波那契子序列長度if (tempAns > ans) {ans = tempAns;}}}// 如果找到了斐波那契子序列，返回長度加上初始的兩個數if (ans > 0) {return ans + 2;} else {return ans;}}
}// 示例用法
const solution = new Solution();
// 輸出最長斐波那契子序列的長度
console.log(solution.lenLongestFibSubseq([1, 2, 3, 4, 5, 6, 7, 8]));