子串：連續的
子序列：不需要連續
DP總覽
標準問法
計數（多少種路徑...）
- Li114，多少種路徑
- 多少種方法選出k個數，使得和是sum
最值（最大利潤、最小數量、最長子串...）
- Li669，硬幣的最少個數
- Li076，最長上升子序列
存在性（可行性、能否）
- Li116，能否跳到最后一塊石頭
問題特點
- 可以變成子問題（最優子結構）
- 子問題之間存在重復計算
解題步驟
-
確定狀態
- 考慮最后一步（最后一個物品，最后一個路徑，最后一個部分）
- 變成解決子問題了（規模更小的問題）
- 狀態就是計算大問題時必要的子問題的資訊
-
確定狀態轉移方程
- ? dp[i] 和 f(i) 不完全一樣
P2O_2e 14，Li515 - dp[i]的計算順序（從大到小還是從小到達）有影響
0-1背包
- ? dp[i] 和 f(i) 不完全一樣
-
處理初始條件和邊界情況
- 初始條件：開始的幾項（用不了轉移方程求解的就是初始條件）
- 邊界情況：
- 陣列下標越界時
- 情況不存在時的dp值（比如股票問題的負無窮）
注意計算dp的順序
- 原則就是計算需要的資料都是之前計算的結果，以及別覆寫還要用的資料（壓縮空間時注意）
- 一般都是從小到大，背包問題的空間優化必須反向計算
空間優化
- 使用滾動陣列, 根據狀態轉移方程中需要的最舊的資料確定大小
- 先寫出不壓縮的，然后用
dp[i % n]代替dp[i]是最方便, 最好理解的解決辦法, 其中n是壓縮后的陣列大小，用個變數名cur = i % n更容易修改 - 一般是逐行掃描, 滾動陣列長度是列數的倍數， 如果列多行少時, 可以考慮逐列掃描讓滾動陣列長度是列數的倍數， 進一步優化空間
坐標型20%
問題特點
- 條件： 一般給矩陣
- 狀態定義 ： 狀態dp[i]的含義是以a[i]結尾的序列的性質
- 轉移方程 : /
- 回傳 ： 最后回傳dp[n - 1]
刷題記錄
| Leet | Lintcode | 簡介 | TO | SO | 識訓 |
|---|---|---|---|---|---|
| L62 | Li114 | 不同路徑 | |||
| L63 | Li115 | 不同路徑，網格中有障礙 | |||
| L64 | Li110 | 路徑上數字和的最小值 | |||
| Lv361 | Li553 | 炸彈襲擊 | 1. 分解成4個方向，分別記錄狀態； 2. 記錄狀態時，敵人和墻也可以炸 |
序列型20%
問題特點
-
條件 ： 一般給一維陣列
-
狀態定義 ： 狀態dp[i]的含義是前i個元素的序列的性質
-
轉移方程 ： 這種狀態定義下對應的轉移方程，?for回圈是
i <= n（ 經常寫成i < n，導致輸出0） -
回傳 ： 最后回傳dp[n]
刷題記錄
| Leet | Lint | 簡介 | TO | SO | 識訓 |
|---|---|---|---|---|---|
| Lv256 | Li515 | 刷房子 | |||
| Lv265 | Li556 | 刷房子，k種顏色 | O(n*k) |
||
| L198 | Li392 | 打家劫舍 | |||
| L213 | Li534 | 打家劫舍II 環形街區 | |||
| L121 | Li149 | 買賣股票的最佳時機（一次交易） | |||
| L122 | Li150 | 買賣股票的最佳時機II（多次交易） | |||
| L123 | Li151 | 買賣股票的最佳時機III（2次交易） | |||
| L188_L面63 | Li393 | 買賣股票的最佳時機IIII（k次交易） | |||
| L338 | Li664 | 一個范圍內所有的數，各自的數位中1的個數 |
劃分型20%
問題特點
- 條件 ： 一般字串或陣列
- 狀態定義 ： 狀態dp[i]用坐標型的含義
- 轉移方程 ： dp[i]時列舉最后一段的可能的起點
- 回傳：dp[n - 1]
刷題記錄
| Leet | Lint | 簡介 | TO | SO | 識訓 |
|---|---|---|---|---|---|
| L91 | Li512 | 編碼決議方法 | |||
| L279 | Li513 | 最少平方數 | O(n^3/2) | 最優解 ??四平方數和定理 | |
| L132 | Li108 | 分割回文串 | O(n^2) | 中軸方法判斷回文串 | |
| / | Li437????? | 抄書 | 最優解 ??貪心二分 求和Trick |
||
| L55 | Li116 | 跳躍石頭 | O(n^2) | 最優解 ??貪心 |
子序列型5%
LIS：Longest Increasing Subsequence
問題特點
- 條件 ： 字串或陣列
- 狀態定義 ： 狀態dp[i]用坐標型的含義
- 轉移方程 ： /
- 回傳 ： ?dp[0] ~ dp[n - 1]中的最大值
刷題記錄
| Leet | Lint | 簡介 | 時間復雜度 | 空間復雜度 | 識訓 |
|---|---|---|---|---|---|
| L300 | Li076 | 最長上升子序列 | O(N^2) |
??patience game解法O(N*logN) |
|
| L53 | Li41 | 最大連續子序列和 | |||
| L354 | Li602 | 信封套娃（和最長上升子序列解法一樣） | ??O(N*logN) |
||
| / | Li397 | 最長單向（上升或下降）連續子序列（最長單向子串） | 上升下降分別求 |
區間型15%
子問題需要去頭去尾
問題特點
- 條件 ： 字串或陣列
- 狀態定義 ：
dp[i][j]， 字符i到j的區間的性質 - 轉移方程 ： 回圈變數是區間的長度
- 回傳 ：
dp[0][n - 1]
刷題記錄
| Leet | Lint | 簡介 | 時間復雜度 | 空間復雜度 | 識訓 |
|---|---|---|---|---|---|
| L516 | Li667 | 最長回文子序列 | O(N^2) |
||
| L877 | LiV396 | 只能從兩端取數，誰的和最大誰贏 | |||
| L87 | Li430 | 擾亂字串????? | |||
| L312 | Li168 | 戳氣球(消去型->區間型)????? |
背包型10%
載重W的背包，N件待選物品，物品屬性：重量w，價值v
問題特點
- 條件 ： 陣列
- 狀態定義 ： 狀態dp[i]用序列型的含義，重量一定要記錄在狀態中
- 轉移方程：最后一步是最后一個物品 是否進入背包(0-1) / 是哪一個(完全)
- 回傳 ：/
分類
問法分類
- 可行型
- 最值型
- 要求正好裝滿
- 不要求正好裝滿
- 計數型
要求分類
-
0-1背包，串列中的物品只有一個
-
完全背包，串列中的物品有任意個
刷題記錄
| Leet | Lint | 簡介 | 時間復雜度 | 空間復雜度 | 識訓 |
|---|---|---|---|---|---|
| / | Li92 | 最值型0-1背包，最大重量 | |||
| Li125 | 最值型0-1背包，最大價值 | ||||
| / | Li563 | 計數型0-1背包，裝滿的方案數 | |||
| Li562 | 計數型完全背包，裝滿的方案數（不同順序算一種方案） | ||||
| / | Li564 | 計數型完全背包，和為指定值的組合數（不同順序算不同方案） | 描述更復雜解決卻更簡單（股票問題也是） | ||
| L332 | Li669 | 最值型完全背包，換硬幣的最少個數 | |||
| LiV440 | 最值型完全背包，最大價值 |
博弈型5%
問題特點
從第一步開始考慮而不是最后一步
弄清楚必勝態，必敗態
刷題記錄
| Leet | Lint | 簡介 | 時間復雜度 | 空間復雜度 | 識訓 |
|---|---|---|---|---|---|
| / | Li394 | 誰最后沒東西拿誰輸 | O(N) |
||
| L877 | LiV396 | 只能從兩端取數，誰的和最大誰贏 |
雙序列型
問題特點
- 條件 ： 字串或陣列
- 狀態定義 ：
dp[i][j]， 第一個序列的前i個字符和第二個序列的前j個字符的性質 - 轉移方程 ：最后一步，考慮怎么砍尾巴
- 回傳 ：
dp[m][n]
刷題記錄
| Leet | Lint | 簡介 | 時間復雜度 | 空間復雜度 | 識訓 |
|---|---|---|---|---|---|
| L1143 | Li77 | 最長公共子序列LCS | |||
| L97 | Li29 | 交錯字串Iterleaving String | |||
| L72 | Li119 | 最小編輯距離Edit Distance |
綜合型5%
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/49761.html
標籤：其他
下一篇：華為云服務器使用評測