線性DP(動態規劃)

線性DP的概念（視頻）

學習線性DP之前，請確保已經對遞推有所了解。

一、概念

1、動態規劃

不要去看網上的各種概念，什么無后效性，什么空間換時間，會越看越暈。從做題的角度去理解就好了，動態規劃就可以理解成一個 有限狀態自動機，從一個初始狀態，通過狀態轉移，跑到終止狀態的過程。

2、線性動態規劃

線性動態規劃，又叫線性DP，就是在一個線性表上進行動態規劃，更加確切的說，應該是狀態轉移的過程是在線性表上進行的。我們考慮有 0 到 n 這 n+1 個點，對于第 i 個點，它的值取決于 0 到 i-1 中的某些點的值，可以是求最大值、最小值、方案數等等。

很明顯，如果一個點 i 可以從 i-1 或者 i-2 過來，求到達第 i 號點的方案數，就是我們之前學過的斐波那契數列了，具體可以參考這篇文章：遞推。

二、例題解析

1、題目描述

給定一個?n，再給定一個?n(n ≤ 1000) 個整數的數組? cost，其中?cost[i]?是從樓梯第?i?個臺階向上爬需要支付的費用。一旦支付此費用，即可選擇向上爬 1個或者 2個臺階。可以選擇從下標為?0?或下標為?1?的臺階開始爬樓梯，請計算并返回達到樓梯頂部的最低花費。

2、算法分析

我們發現這題和之前的爬樓梯很像，只不過從原來的計算 方案數 變成了計算 最小花費。嘗試用一個數組來表示狀態：f[i] 表示爬到第 i 層的最小花費。

由于每次只能爬 1個或者 2個臺階，所以 f[i] 這個狀態只能從 f[i-1] 或者 f[i-2] 轉移過來：

1）如果從 i-1 層爬上來，需要的花費就是 f[i-1] + cost[i-1]；

2）如果從 i-2 層爬上來，需要的花費就是 f[i-2] + cost[i-2]；

沒有其他情況了，而我們要求的是最小花費，所以 f[i] 就應該是這兩者的小者，得出狀態轉移方程：

f[i] = min(f[i-1] + cost[i-1], f[i-2] + cost[i-2])

然后考慮一下初始情況 f[0] 和 f[1]，根據題目要求它們都應該是 0。

3、源碼詳解

int min(int a, int b) {return a < b ? a : b;                   // (1)
}int minCostClimbingStairs(int* cost, int n){int i;                                  // (2)int f[1001] = {0, 0};                   // (3)for(i = 2; i <= n; ++i) {               // (4)f[i] = min(f[i-1] + cost[i-1], f[i-2] + cost[i-2]);}return f[n];                            // (5)
}

(1) 為了方便求最小值，我們實現一個最小值函數 min，直接利用 C語言的條件運算符就可以了；
(2) 然后開始動態規劃的求解，首先定義一個循環變量；
(3) 再定義一個數組 f[i] 代表從第 0 階爬到第 i 階的最小花費，并且初始化第 0 項和第 1 項；
(4) 然后一個 for 循環，從第 2 項開始，直接套上狀態轉移方程就能計算每一項的值了；
(5) 最后返回第 n 項即可；

三、再談動態規劃

經典的線性DP有很多，比如：最長遞增子序列、背包問題是非常經典的線性DP了。建議先把線性DP搞清楚以后再去考慮其它的動態規劃問題。

而作為動態規劃的通解，主要分為以下幾步：

????1、設計狀態

????2、寫出狀態轉移方程

????3、設定初始狀態

????4、執行狀態轉移

????5、返回最終的解

一、基本概念

學習動態規劃，如果一上來告訴你：最優子結構、重疊子問題、無后效性這些抽象的概念，那么你可能永遠都學不會這個算法，最好的方法就是從一些簡單的例題著手，一點一點去按照自己的方式理解，而不是背概念。

對于動態規劃問題，最簡單的就是線性動態規劃，這堂課我們就利用一些，非常經典的線性動態規劃問題來進行分析，從而逐個擊破。

二、常見問題

1、爬樓梯

問題描述：有一個 n 級樓梯，每次可以爬 1 或者 2 級。問有多少種不同的方法可以爬到第 n 級。
狀態：dp[i] 表示爬到第 i 級樓梯的方案數。
初始狀態：dp[0] = dp[1] = 1
狀態轉移方程：dp[i] = dp[i-1] + dp[i-2]。（對于爬到第 i 級，可以從 i-1 級樓梯爬過來，也可以從 i-2 級樓梯爬過來）
狀態數：O(n)
狀態轉移消耗：O(1)

時間復雜度：O(n)

class Solution {
public:int climbStairs(int n) {vector<int> dp(n+1);dp[0] = dp[1] = 1;for (int i = 2; i < dp.size(); i++)dp[i] = dp[i - 1] + dp[i - 2];return dp[n];}
};

2、最大子數組和（最大子段和）

問題描述：給定一個 n 個元素的數組 arr[]，求一個子數組，并且它的元素和最大，返回最大的和。
狀態：dp[i] 表示以第 i 個元素結尾的最大子數組和。
初始狀態：dp[0] = arr[0]（可以為負數）
狀態轉移方程：dp[i] = arr[i] + max(dp[i-1], 0)。（因為是以第i個元素結尾，所以 arr[i]必選， dp[i-1] 這部分是以第 i-1 個元素結尾的，可以不選或者選，完全取決于它是否大于0，所以選和不選取大者）
狀態數：O(n)
狀態轉移消耗：O(1)
時間復雜度：O(n)

class Solution {
public:int maxSubArray(vector<int>& arr) {vector<int> dp(arr.size()+1);dp[0] = arr[0];int maxSum=dp[0];for(int i=1;i<arr.size();i++){dp[i] = arr[i] + max(dp[i-1], 0);maxSum = max(maxSum, dp[i]);}return maxSum;}
};還有一個雙O(1)的方法
class Solution {
public:int maxSubArray(vector<int>& arr) {if (arr.empty()) return 0;int currentSum = arr[0];int maxSum = arr[0];for (int i = 1; i < arr.size(); ++i) {currentSum = max(currentSum + arr[i], arr[i]);maxSum = max(maxSum, currentSum);}return maxSum;}
};

3、最長遞增子序列

問題描述：給定一個 n 個元素的數組 arr[]，求一個最大的子序列的長度，序列中元素單調遞增。
狀態：dp[i] 表示以第 i 個元素結尾的最長遞增子序列的長度。
初始狀態：dp[0] = 1
狀態轉移方程：dp[i] = max(dp[i], dp[j] + 1)。(arr[j] < arr[i]) （對于所有下標比 i 小的下標 j，并且滿足 arr[j] < arr[i] 的情況，取所有這里面 dp[j] 的最大值加上 1 就是 dp[i] 的值，當然可能不存在這樣的 j，那么這時候 dp[i] 的值就是 1）
狀態數：O(n)
狀態轉移消耗：O(n)
時間復雜度：O(n^2)

class Solution {
public:int lengthOfLIS(vector<int>& nums) {vector<int> dp(nums.size(), 1);int maxlength = 1;for (int i = 1; i < nums.size(); i++) {for (int j = 0; j < i; j++) {if (nums[j] < nums[i]) {dp[i] = max(dp[i], dp[j] + 1);maxlength = max(maxlength, dp[i]);}}}return maxlength;}
};

4、數字三角形

問題描述：給定一個 n 行的三角形 triangle[][]，找出自頂向下的最小路徑和。每一步只能移動到下一行中相鄰的結點上。相鄰的結點 在這里指的是下標與 上一層結點下標 相同或者等于 上一層結點下標 + 1 的兩個結點。也就是說，如果正位于當前行的下標 i ，那么下一步可以移動到下一行的下標 i 或 i + 1。
狀態：dp[i][j] 表示從頂部走到 (i, j) 位置的最小路徑和。
初始狀態：dp[0][0] = triangle[0][0]；起點就是頂部，路徑和只能是它自己。
狀態轉移方程：dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]。（走到 (i,j) 的路徑只能從兩個方向來：從左上方來（即從 (i-1, j-1) 走到 (i,j)）從上方來（即從 (i-1, j) 走到 (i,j)）所以我們只需要比較這兩個方向的最小值，加上當前位置的值即可。）
狀態數：O(n^2)
狀態轉移消耗：O(1)
時間復雜度：O(n^2)


class Solution {
public:int minimumTotal(vector<vector<int>>& triangle) {int n = triangle.size();vector<vector<int>> dp(n, vector<int>(n, 0));int minsum = 0;dp[0][0] = triangle[0][0];for (int i = 1; i < triangle.size(); i++) {for (int j = 0; j < triangle[i].size(); j++) {if (j == 0)dp[i][j] = dp[i - 1][j] + triangle[i][j];else if (j == i)dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];elsedp[i][j] =min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];}}return *min_element(dp[n - 1].begin(), dp[n - 1].end());}
};

5、股票系列

力扣有一些非常經典的股票問題，可以自己嘗試去看一下。?

121. 買賣股票的最佳時機這個解法不是dp

class Solution {
public:int maxProfit(vector<int>& prices) {int cost = INT_MAX, profit = 0;for (int price : prices) {cost = min(cost, price);profit = max(profit, price - cost);}return profit;}
};

122. 買賣股票的最佳時機 II

?你需要在每一天決定是否買、賣、或不操作股票，最終獲得最大利潤。
限制條件：任何時候最多只能持有一股股票（即必須先賣出才能再買）。

我們每天的狀態只有兩種可能：

狀態 0： 手里沒有股票（可以買）
狀態 1： 手里有股票（可以賣）

我們用一個二維數組 dp[i][0] 和 dp[i][1] 來記錄第 i 天結束后，這兩種狀態下的 最大利潤 。

從第 i-1 天的狀態推導第 i 天的狀態?

(1) 當前狀態 0（手里沒有股票）

可能來源：
- 昨天也沒股票（今天沒買），利潤不變：dp[i-1][0]
- 昨天有股票（今天賣了），利潤 = 昨天有股票的利潤 + 今天賣出的價格：dp[i-1][1] + prices[i]
取最大值：dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])

(2) 當前狀態 1（手里有股票）

可能來源：
- 昨天也有股票（今天沒賣），利潤不變：dp[i-1][1]
- 昨天沒股票（今天買了），利潤 = 昨天沒股票的利潤 - 今天買入的價格：dp[i-1][0] - prices[i]
取最大值：dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])

4. 初始狀態

第 0 天（第一天）：
- dp[0][0] = 0（沒有買，利潤為 0）
- dp[0][1] = -prices[0]（買了，但還沒賣，利潤為負）

5. 最終答案

最后一天 不持有股票 的利潤一定是最大的（因為持有股票還沒賣的話，利潤可能不是最大）：return dp[n-1][0] // n 是天數

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();vector<vector<int>> dp(n, vector<int>(2, 0));// 初始狀態dp[0][0] = 0;dp[0][1] = -prices[0];for (int i = 1; i < n; ++i) {dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]);}return dp[n-1][0];  // 返回最后一天不持有股票的最大利潤}
};

123. 買賣股票的最佳時機 III

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();vector<vector<int>> dp(n, vector<int>(4));dp[0][0] = -prices[0], dp[0][1] = 0, dp[0][2] = -prices[0],dp[0][3] = 0;for (int i = 1; i < n; i++) {dp[i][0] = max(-prices[i], dp[i - 1][0]);dp[i][1] = max(dp[i - 1][0] + prices[i], dp[i - 1][1]);dp[i][2] = max(dp[i - 1][1] - prices[i], dp[i - 1][2]);dp[i][3] = max(dp[i - 1][2] + prices[i], dp[i - 1][3]);}return max(dp[n - 1][1], dp[n - 1][3]);}
};

188. 買賣股票的最佳時機 IV

fucking-algorithm/動態規劃系列/團滅股票問題.md at master · labuladong/fucking-algorithm

309. 買賣股票的最佳時機含冷凍期

714. 買賣股票的最佳時機含手續費

6、最短路徑問題

Dijkstra 本質也是一個動態規劃問題。只不過通過不斷更新狀態，來實現狀態轉移。

7、背包問題

0/1背包DP

完全背包DP

三、細節剖析

1、問題求什么，狀態就盡量定義成什么，有了狀態，再去盡力套狀態轉移方程。

2、動態規劃的時間復雜度等于狀態數 x 狀態轉移的消耗；

3、狀態轉移方程中的 i 變量導致數組下標越界，從而可以確定哪些狀態是初始狀態；

4、狀態轉移的過程一定是單向的，把每個狀態理解成一個結點，狀態轉移理解成邊，動態規劃的求解就是在一個有向無環圖上進行遞推計算。

5、因為動態規劃的狀態圖是一個有向無環圖，所以一般會和拓撲排序聯系起來。

?題目

接龍數列

數組切分

最大魅力值

0、自然語言視頻題解

接龍數列
數組切分
最大魅力值

3、C++視頻題解

接龍數列
數組切分
最大魅力值

　　使用最小花費爬樓梯

　　打家劫舍

　　刪除并獲得點數

　　買賣股票的最佳時機(帶字幕版)

遞推

斐波那契數

第 N 個泰波那契數

劍指 Offer 10- II. 青蛙跳臺階問題

三步問題

劍指 Offer 10- I. 斐波那契數列

爬樓梯

劍指 Offer II 003. 前 n 個數字二進制中 1 的個數

旋轉函數

訪問完所有房間的第一天

線性DP / 狀態轉移 O(C)

使用最小花費爬樓梯

劍指 Offer II 088. 爬樓梯的最少成本

解決智力問題

打家劫舍

劍指 Offer II 089. 房屋偷盜

按摩師

打家劫舍 II

劍指 Offer II 090. 環形房屋偷盜

劍指 Offer 46. 把數字翻譯成字符串

解碼方法

1 比特與 2 比特字符

使序列遞增的最小交換次數

恢復數組

秋葉收藏集

刪除并獲得點數

完成比賽的最少時間

線性DP / 狀態轉移 O(n)

單詞拆分

分隔數組以得到最大和

最低票價

跳躍游戲 II

帶因子的二叉樹

最大子數組和

劍指 Offer 42. 連續子數組的最大和

連續數列

最大子數組和

任意子數組和的絕對值的最大值

乘積最大子數組

乘積為正數的最長子數組長度

刪除一次得到子數組最大和

最長遞增子序列

最長數對鏈

最長遞增子序列的個數

擺動序列

最長湍流子數組

最長遞增子序列

最長字符串鏈

堆箱子

俄羅斯套娃信封問題

馬戲團人塔

使數組 K 遞增的最少操作次數

股票問題

股票平滑下跌階段的數目

買賣股票的最佳時機 II

買賣股票的最佳時機含手續費

最佳買賣股票時機含冷凍期

買賣股票的最佳時機 III

前綴最值

有效的山脈數組

將每個元素替換為右側最大元素

買賣股票的最佳時機

最佳觀光組合

數組中的最長山脈

適合打劫銀行的日子

兩個最好的不重疊活動

接雨水

移除所有載有違禁貨物車廂所需的最少時間

接雨水 II

前綴和

分割字符串的最大得分

哪種連續子字符串更長

翻轉字符

將字符串翻轉到單調遞增

刪掉一個元素以后全為 1 的最長子數組

和為奇數的子數組數目

兩個非重疊子數組的最大和

K 次串聯后最大子數組之和

找兩個和為目標值且不重疊的子數組

生成平衡數組的方案數

三個無重疊子數組的最大和

統計特殊子序列的數目