> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/topics/dynamic-programming.md).

# Dynamic programming

<http://blog.csdn.net/linhuanmars/article/details/38468361>

```
DP:
1.状态:即定义,中间的状态
 2.方程:即从前一种状态推出现在的状态.
 3.初始化:极限小的状态,即为起点.
 4.答案:终点

 递归：
 1. 定义（状态）
    • 接受什么参数
    • 做了什么事
    • 返回什么值
 2. 拆解（方程）
    • 如何将参数变小
 3. 出口（初始化）
    • 什么时候可以直接 return
```

```
坐标型  20%
序列型  20%
划分型  20%
区间型  15%
背包型  10%
拓扑型  5%
博弈型  5%
综合型  5%
```

## state machine

<https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/>

## 坐标型 20%

f\[i] 第i个

<https://leetcode.com/problems/word-break/description/> <https://leetcode.com/problems/concatenated-words/description/> <https://leetcode.com/problems/unique-paths/>

Divide & conquer, solve with 2 pass: order and reversed order <https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/description/> <https://leetcode.com/problems/bomb-enemy> <https://leetcode.com/problems/maximum-sum-of-3-non-overlapping-subarrays/description/>

LIS problem <https://leetcode.com/problems/longest-increasing-subsequence> <https://leetcode.com/problems/russian-doll-envelopes/description/> <https://leetcode.com/problems/increasing-triplet-subsequence> <https://leetcode.com/problems/maximum-length-of-pair-chain> <https://leetcode.com/problems/number-of-longest-increasing-subsequence> <https://leetcode.com/problems/increasing-subsequences/description/> <https://leetcode.com/problems/longest-continuous-increasing-subsequence/description/>

## 序列型 20%

f\[i] 前i个

* can be O(1) variable or O(n)/1D variable

these problems are conditional, discuss different situation:

<https://leetcode.com/problems/paint-fence/description/> <https://leetcode.com/problems/paint-house/description/> <https://leetcode.com/problems/paint-house-ii/description/> <https://leetcode.com/problems/maximum-vacation-days/description/> <https://leetcode.com/problems/house-robber/> <https://leetcode.com/problems/house-robber-ii/description/> <https://leetcode.com/problems/climbing-stairs/> <https://leetcode.com/problems/maximum-subarray/description/>

局部最优和全局最优 <https://leetcode.com/problems/maximum-product-subarray/description/> <https://leetcode.com/problems/maximum-subarray>

Stocks: the whole series key point: buy and sell must cannot happen together, because if price go down, it's buy point, selling here get 0 profit, meaningless. if price go up, it's sell point, won't buy. buy2 must happen before sell1, because if not, buy2 will be negative, won't update.

```java
buy1 = Math.max(buy1, -prices[i]);
sell1 = Math.max(sell1, buy1 + prices[i]);
buy2 = Math.max(buy2, sell1 - prices[i]);
sell2 = Math.max(sell2, buy2 + prices[i]);
```

<https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/> <https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii> <https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii> <https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/description/> <https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/>

### 双序列型

<https://leetcode.com/problems/edit-distance/> <https://leetcode.com/problems/regular-expression-matching/> <https://leetcode.com/problems/wildcard-matching/description/> <https://leetcode.com/problems/distinct-subsequences/description/> <https://leetcode.com/problems/minimum-window-subsequence/description/> <https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings> <https://leetcode.com/problems/delete-operation-for-two-strings>

## 划分型 20%

<https://leetcode.com/problems/decode-ways/> <https://leetcode.com/problems/decode-ways-ii> <https://leetcode.com/problems/house-robber-iii>

## 区间型 15%

<https://leetcode.com/problems/longest-palindromic-substring/description/>

## 背包型 10% coin change

<https://blog.csdn.net/wzy_1988/article/details/12260343>

<https://leetcode.com/problems/partition-equal-subset-sum/description/> <https://leetcode.com/problems/partition-to-k-equal-sum-subsets/description/> <https://leetcode.com/problems/combination-sum-iv/description/> <https://leetcode.com/problems/coin-change/description/> <https://leetcode.com/problems/target-sum/description/> <https://leetcode.com/problems/ones-and-zeroes/description/> <https://leetcode.com/problems/non-negative-integers-without-consecutive-ones/description/> <https://leetcode.com/problems/non-negative-integers-without-consecutive-ones/description/> <https://leetcode.com/problems/house-robber-ii>

## from 1 to k

<https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/description/> <https://leetcode.com/problems/partition-to-k-equal-sum-subsets/description/> <https://leetcode.com/problems/maximum-sum-of-3-non-overlapping-subarrays/description/>

## subproblem

these problems are not DP, but there ideas are similar: solving subproblem. <https://leetcode.com/problems/count-of-smaller-numbers-after-self/description/> <https://leetcode.com/problems/count-of-range-sum/description/> <https://leetcode.com/problems/reverse-pairs/description/>

## dp + divide\&conquer

it's not only one subproblem, instead, many subproblems need to be compared or processed. <https://leetcode.com/problems/encode-string-with-shortest-length/description/> <https://leetcode.com/problems/unique-binary-search-trees/description/>

## MiniMax problem (3D DP)

most game problem <https://leetcode.com/problems/guess-number-higher-or-lower-ii/description/> <https://leetcode.com/problems/can-i-win/description/>

3 for-loop -> DFS + Memo <https://leetcode.com/problems/split-array-largest-sum/description/> <https://leetcode.com/problems/burst-balloons/>

<https://leetcode.com/problems/largest-sum-of-averages/description/> <https://leetcode.com/problems/knight-probability-in-chessboard/description/>

<https://leetcode.com/problems/encode-string-with-shortest-length/description/>

<https://leetcode.com/discuss/general-discussion/592146/dynamic-programming-summary/513130>

## 1. Number Tower，数塔

1. [118. Pascal's Triangle](https://leetcode.com/problems/pascals-triangle/)`(Easy)`、[118. 杨辉三角](https://leetcode-cn.com/problems/pascals-triangle/)`(简单)`
2. [119. Pascal's Triangle II](https://leetcode.com/problems/pascals-triangle-ii/)`(Easy)`、[119. 杨辉三角 II](https://leetcode-cn.com/problems/pascals-triangle-ii/)`(简单)`
3. [64. Minimum Path Sum](https://leetcode.com/problems/minimum-path-sum/)`(Medium)`、[64. 最小路径和](https://leetcode-cn.com/problems/minimum-path-sum/)`(中等)`
4. [120. Triangle](https://leetcode.com/problems/triangle/)`(Medium)`、[120. 三角形最小路径和](https://leetcode-cn.com/problems/triangle/)`(中等)`
5. [931. Minimum Falling Path Sum](https://leetcode.com/problems/minimum-falling-path-sum/)`(Medium)`、[931. 下降路径最小和](https://leetcode-cn.com/problems/minimum-falling-path-sum/)`(中等)`
6. [1289. Minimum Falling Path Sum II](https://leetcode.com/problems/minimum-falling-path-sum-ii/)`(hard)`、[1289. 下降路径最小和 II](https://leetcode-cn.com/problems/minimum-falling-path-sum-ii/)`(困难)`
7. [1301. Number of Paths with Max Score](https://leetcode.com/problems/number-of-paths-with-max-score/)`(hard)`、[1301. 最大得分的路径数目](https://leetcode-cn.com/problems/number-of-paths-with-max-score/)`(困难)`

## 2. Fibonacci Numbers，斐波那契数列

1. Fibonacci numbers，斐波那契数列问题
   1. [509. Fibonacci Number](https://leetcode.com/problems/fibonacci-number/)`(Easy)`、[509. 斐波那契数](https://leetcode-cn.com/problems/fibonacci-number/)`(简单)`
   2. [1137. N-th Tribonacci Number](https://leetcode.com/problems/n-th-tribonacci-number/)`(Easy)`、[1137. 第 N 个泰波那契数](https://leetcode-cn.com/problems/n-th-tribonacci-number/)`(简单)`
2. Staircase，爬楼梯问题
   1. [70. Climbing Stairs](https://leetcode.com/problems/climbing-stairs/)`(Easy)`、[70. 爬楼梯](https://leetcode-cn.com/problems/climbing-stairs/)`(简单)`
   2. [746. Min Cost Climbing Stairs](https://leetcode.com/problems/min-cost-climbing-stairs/)`(Easy)`、[746. 使用最小花费爬楼梯](https://leetcode-cn.com/problems/min-cost-climbing-stairs/)`(简单)`
3. House thief，偷房子问题
   1. [198. House Robber](https://leetcode.com/problems/house-robber/)`(Easy)`、[198. 打家劫舍](https://leetcode-cn.com/problems/house-robber/)`(简单)`
   2. [213. House Robber II](https://leetcode.com/problems/house-robber-ii/)`(Medium)`、[213. 打家劫舍 II](https://leetcode-cn.com/problems/house-robber-ii/)`(中等)`

## 3. Memory Search，记忆化搜索

1. [139. Word Break](https://leetcode.com/problems/word-break/)`Medium`、[139. 单词拆分](https://leetcode-cn.com/problems/word-break/)`中等`
2. [140. Word Break II](https://leetcode.com/problems/word-break-ii/)`Hard`、[140. 单词拆分 II](https://leetcode-cn.com/problems/word-break-ii/)`困难`
3. [329. 矩阵中的最长递增路径](https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/)`Hard`、[329. 矩阵中的最长递增路径](https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/)`困难`

## 4. 0/1 Knapsack, 0/1 背包

1. Equal Subset Sum Partition，相等子集划分问题
   1. [416. Partition Equal Subset Sum](https://leetcode.com/problems/partition-equal-subset-sum/)`(Medium)`、[416. 分割等和子集](https://leetcode-cn.com/problems/partition-equal-subset-sum/)`(中等)`
2. Subset Sum，子集和问题
   1. [494. Target Sum](https://leetcode.com/problems/target-sum/)`(Medium)`、[494. 目标和](https://leetcode-cn.com/problems/target-sum/)`(中等)`
3. Minimum Subset Sum Difference，子集和的最小差问题
   1. [1049. Last Stone Weight II](https://leetcode.com/problems/last-stone-weight-ii/)`(Medium)`、[1049. 最后一块石头的重量 II](https://leetcode-cn.com/problems/last-stone-weight-ii/)`(中等)`
4. Other，其它
   1. [474. Ones and Zeroes](https://leetcode.com/problems/ones-and-zeroes/)`(Medium)`、[474. 一和零](https://leetcode-cn.com/problems/ones-and-zeroes/)`(中等)`

## 5. Unbounded Knapsack，无限（完全）背包

1. Coin Change，换硬币问题
   1. [322. Coin Change](https://leetcode.com/problems/coin-change/)`(Medium)`、[322. 零钱兑换](https://leetcode-cn.com/problems/coin-change/)`(中等)`
   2. [518. Coin Change 2](https://leetcode.com/problems/coin-change-2/)`(Medium)`、[518. 零钱兑换 II](https://leetcode-cn.com/problems/coin-change-2/)`(中等)`
2. Others，其它
   1. [377. Combination Sum IV](https://leetcode.com/problems/combination-sum-iv/)`(Medium)`、[377. 组合总和 Ⅳ](https://leetcode-cn.com/problems/combination-sum-iv/)`(中等)`
   2. [638. Shopping Offers](https://leetcode.com/problems/shopping-offers/)`(Medium)`、[638. 大礼包](https://leetcode-cn.com/problems/shopping-offers/)`(中等)`
   3. [1449. Form Largest Integer With Digits That Add up to Target](https://leetcode.com/problems/form-largest-integer-with-digits-that-add-up-to-target/)`(Hard)`、[1449. 数位成本和为目标值的最大数字](https://leetcode-cn.com/problems/form-largest-integer-with-digits-that-add-up-to-target/)`(困难)`

## 6. Counting DP，计数 DP

1. [62. Unique Paths](https://leetcode.com/problems/unique-paths/)`(Medium)`、[62. 不同路径](https://leetcode-cn.com/problems/unique-paths/)`(中等)`
2. [63. Unique Paths II](https://leetcode.com/problems/unique-paths-ii/)`(Medium)`、[63. 不同路径 II](https://leetcode-cn.com/problems/unique-paths-ii/)`(中等)`
3. [91. Decode Ways](https://leetcode.com/problems/decode-ways/)`(Medium)`、[91. 解码方法](https://leetcode-cn.com/problems/decode-ways/)`(中等)`
4. [576. Out of Boundary Paths](https://leetcode.com/problems/out-of-boundary-paths/)`(Medium)`、[576. 出界的路径数](https://leetcode-cn.com/problems/out-of-boundary-paths/)`(中等)`
5. [790. Domino and Tromino Tiling](https://leetcode.com/problems/domino-and-tromino-tiling/)`(Medium)`、[790. 多米诺和托米诺平铺](https://leetcode-cn.com/problems/domino-and-tromino-tiling/)`(中等)`
6. [935. Knight Dialer](https://leetcode.com/problems/knight-dialer/)`(Medium)`、[935. 骑士拨号器](https://leetcode-cn.com/problems/knight-dialer/)`(中等)`
7. [1155. Number of Dice Rolls With Target Sum](https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/)`(Medium)`、[1155. 掷骰子的 N 种方法](https://leetcode-cn.com/problems/number-of-dice-rolls-with-target-sum/)`(中等)`
8. [1641. Count Sorted Vowel Strings](https://leetcode.com/problems/count-sorted-vowel-strings/)`(Medium)`、[1641. 统计字典序元音字符串的数目](https://leetcode.com/problems/count-sorted-vowel-strings/)`(中等)`
9. [1220. Count Vowels Permutation](https://leetcode.com/problems/count-vowels-permutation/)`(Hard)`、[1220. 统计元音字母序列的数目](https://leetcode-cn.com/problems/count-vowels-permutation/)`(困难)`
10. [1223. Dice Roll Simulation](https://leetcode.com/problems/dice-roll-simulation/)`(Medium)`、[1223. 掷骰子模拟](https://leetcode-cn.com/problems/dice-roll-simulation/)`(中等)`
11. [552. Student Attendance Record II](https://leetcode.com/problems/student-attendance-record-ii/)`(Hard)`、[552. 学生出勤记录 II](https://leetcode-cn.com/problems/student-attendance-record-ii/)`(困难)`
12. [1269. Number of Ways to Stay in the Same Place After Some Steps](https://leetcode.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps/)`(Hard)`、[1269. 停在原地的方案数](https://leetcode-cn.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps/)`(困难)`
13. [1420. Build Array Where You Can Find The Maximum Exactly K Comparisons](https://leetcode.com/problems/build-array-where-you-can-find-the-maximum-exactly-k-comparisons/)`(Hard)`、[1420. 生成数组](https://leetcode-cn.com/problems/build-array-where-you-can-find-the-maximum-exactly-k-comparisons/)`(困难)`
14. [1575. Count All Possible Routes](https://leetcode.com/problems/count-all-possible-routes/)`(Hard)`、[1575. 统计所有可行路径](https://leetcode-cn.com/problems/count-all-possible-routes/)`(困难)`
15. [1639. Number of Ways to Form a Target String Given a Dictionary](https://leetcode.com/problems/number-of-ways-to-form-a-target-string-given-a-dictionary/)`(Hard)`、[5542. 通过给定词典构造目标字符串的方案数](https://leetcode-cn.com/problems/number-of-ways-to-form-a-target-string-given-a-dictionary/)`(困难)`

## 7. Probability DP，概率 DP

1. [688. Knight Probability in Chessboard](https://leetcode.com/problems/knight-probability-in-chessboard/)`(Medium)`、[688-cn. “马”在棋盘上的概率](https://leetcode-cn.com/problems/knight-probability-in-chessboard/)`(中等)`
2. [808. Soup Servings](https://leetcode.com/problems/soup-servings/)`(Medium)`、[808. 分汤](https://leetcode-cn.com/problems/soup-servings/)`(中等)`

## 8. Tree DP，树状 DP

1. [96. Unique Binary Search Trees](https://leetcode.com/problems/unique-binary-search-trees/)`(Medium)`、[96. 不同的二叉搜索树](https://leetcode-cn.com/problems/unique-binary-search-trees/)`(中等)`
2. [823. Binary Trees With Factors](https://leetcode.com/problems/binary-trees-with-factors/)`(Medium)`、[823. 带因子的二叉树](https://leetcode-cn.com/problems/binary-trees-with-factors/)`(中等)`
3. [1130. Minimum Cost Tree From Leaf Values](https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/)`(Medium)`、[1130. 叶值的最小代价生成树](https://leetcode-cn.com/problems/minimum-cost-tree-from-leaf-values/)`(中等)`
4. [968. Binary Tree Cameras](https://leetcode.com/problems/binary-tree-cameras/)`(Hard)`、[968. 监控二叉树](https://leetcode-cn.com/problems/binary-tree-cameras/)`(困难)`

## 9. Optimal Solution，最优解问题

1. Math，数学相关
   1. [279. Perfect Squares](https://leetcode.com/problems/perfect-squares/)`(Medium)`、[279. 完全平方数](https://leetcode-cn.com/problems/perfect-squares/)`(中等)`
   2. [368. Largest Divisible Subset](https://leetcode.com/problems/largest-divisible-subset/)`(Medium)`、[368. 最大整除子集](https://leetcode-cn.com/problems/largest-divisible-subset/)`(中等)`
   3. [646. Maximum Length of Pair Chain](https://leetcode.com/problems/maximum-length-of-pair-chain/)`(Medium)`、[646. 最长数对链](https://leetcode-cn.com/problems/maximum-length-of-pair-chain/)`(中等)`
   4. [650. 2 Keys Keyboard](https://leetcode.com/problems/2-keys-keyboard/)`(Medium)`、[650. 只有两个键的键盘](https://leetcode-cn.com/problems/2-keys-keyboard/)`(中等)`
   5. [801. Minimum Swaps To Make Sequences Increasing](https://leetcode.com/problems/minimum-swaps-to-make-sequences-increasing/)`(Medium)`、[801. 使序列递增的最小交换次数](https://leetcode-cn.com/problems/minimum-swaps-to-make-sequences-increasing/)`(中等)`
   6. [813. Largest Sum of Averages](https://leetcode.com/problems/largest-sum-of-averages/)`(Medium)`、[813. 最大平均值和的分组](https://leetcode-cn.com/problems/largest-sum-of-averages/)`(中等)`
   7. [1262. Greatest Sum Divisible by Three](https://leetcode.com/problems/greatest-sum-divisible-by-three/)`(Medium)`、[1262. 可被三整除的最大和](https://leetcode-cn.com/problems/greatest-sum-divisible-by-three/)`(中等)`
   8. [1537. Get the Maximum Score](https://leetcode.com/problems/get-the-maximum-score/)`(Hard)`、[1537. 最大得分](https://leetcode-cn.com/problems/get-the-maximum-score/)`(困难)`
2. Buy and Sell Stock，股票买卖问题
   1. [309. Best Time to Buy and Sell Stock with Cooldown](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/)`(Medium)`、[309. 最佳买卖股票时机含冷冻期](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/)`(中等)`
   2. [714. Best Time to Buy and Sell Stock with Transaction Fee](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/)`(Medium)`、[714. 买卖股票的最佳时机含手续费](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/)`(中等)`
   3. [983. Minimum Cost For Tickets](https://leetcode.com/problems/minimum-cost-for-tickets/)`(Medium)`、[983. 最低票价](https://leetcode-cn.com/problems/minimum-cost-for-tickets/)`(中等)`
   4. [123. Best Time to Buy and Sell Stock III](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/)`(Hard)`、[123. 买卖股票的最佳时机 III](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/)`(困难)`
   5. [188. Best Time to Buy and Sell Stock IV](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/)`(Hard)`、[188. 买卖股票的最佳时机 IV](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/)`(困难)`
3. Paint House，粉刷房子问题
   1. [256. Paint House](https://leetcode.com/problems/paint-house/)`(Easy)`、[256. 粉刷房子](https://leetcode-cn.com/problems/paint-house/)`(简单)`
   2. [265. Paint House II](https://leetcode.com/problems/paint-house-ii/)`(Hard)`、[265. 粉刷房子 II](https://leetcode-cn.com/problems/paint-house-ii/)`(困难)`
   3. [1473. Paint House III](https://leetcode.com/problems/paint-house-iii/)`(Hard)`、[1473. 给房子涂色 III](https://leetcode-cn.com/problems/paint-house-iii/)`(困难)`
4. Job Schedule，工作计划问题
   1. [1235. Maximum Profit in Job Scheduling](https://leetcode.com/problems/maximum-profit-in-job-scheduling/)`(Hard)`、[1235. 规划兼职工作](https://leetcode-cn.com/problems/maximum-profit-in-job-scheduling/)`(困难)`
   2. [1335. Minimum Difficulty of a Job Schedule](https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/)`(Hard)`、[1335. 工作计划的最低难度](https://leetcode-cn.com/problems/minimum-difficulty-of-a-job-schedule/)`(困难)`
5. Minimum Number of Operations，最少操作次数问题
   1. [1187. Make Array Strictly Increasing](https://leetcode.com/problems/make-array-strictly-increasing/)`(Hard)`、[1187. 使数组严格递增](https://leetcode-cn.com/problems/make-array-strictly-increasing/)`(困难)`
   2. [514. Freedom Trail](https://leetcode.com/problems/freedom-trail/)`(Hard)`、[514. 自由之路](https://leetcode-cn.com/problems/freedom-trail/)`(困难)`

## 10. Can I Win? 博弈 DP

1. [292. Nim Game](https://leetcode.com/problems/nim-game/)`(Easy)`、[292. Nim 游戏](https://leetcode-cn.com/problems/nim-game/)`(简单)`
2. [1025. Divisor Game](https://leetcode.com/problems/divisor-game/)`(Easy)`、[1025. 除数博弈](https://leetcode-cn.com/problems/divisor-game/)`(简单)`
3. [464. Can I Win](https://leetcode.com/problems/can-i-win/)`(Medium)`、[464. 我能赢吗](https://leetcode-cn.com/problems/can-i-win/)`(中等)`
4. [486. Predict the Winner](https://leetcode.com/problems/predict-the-winner/)`(Medium)`、[486. 预测赢家](https://leetcode-cn.com/problems/predict-the-winner/)`(中等)`
5. [877. Stone Game](https://leetcode.com/problems/stone-game/)`(Medium)`、[877. 石子游戏](https://leetcode-cn.com/problems/stone-game/)`(中等)`
6. [1140. Stone Game II](https://leetcode.com/problems/stone-game-ii/)`(Medium)`、[1140. 石子游戏 II](https://leetcode-cn.com/problems/stone-game-ii/)`(中等)`
7. [1406. Stone Game III](https://leetcode.com/problems/stone-game-iii/)`(Hard)`、[1406. 石子游戏 III](https://leetcode-cn.com/problems/stone-game-iii/)`(困难)`
8. [1510. Stone Game IV](https://leetcode.com/problems/stone-game-iv/)`(Hard)`、[1510. 石子游戏 IV](https://leetcode-cn.com/problems/stone-game-iv/)`(困难)`

## 11. Interval DP，区间 DP

1. Intervals Merge，区间合并
   1. [312. Burst Balloons](https://leetcode.com/problems/burst-balloons/)`(Hard)`、[312. 戳气球](https://leetcode-cn.com/problems/burst-balloons/)`(困难)`
   2. [546. Remove Boxes](https://leetcode.com/problems/remove-boxes/)`(Hard)`、[546. 移除盒子](https://leetcode-cn.com/problems/remove-boxes/)`(困难)`
   3. [664. Strange Printer](https://leetcode.com/problems/strange-printer/)`(Hard)`、[664. 奇怪的打印机](https://leetcode-cn.com/problems/strange-printer/)`(困难)`
   4. [1478. Allocate Mailboxes](https://leetcode.com/problems/allocate-mailboxes/)`(Hard)`、[1478. 安排邮筒](https://leetcode-cn.com/problems/allocate-mailboxes/)`(困难)`
   5. [1547. Minimum Cost to Cut a Stick](https://leetcode.com/problems/minimum-cost-to-cut-a-stick/)`(Hard)`、[1547. 切棍子的最小成本](https://leetcode-cn.com/problems/minimum-cost-to-cut-a-stick/)`(困难)`
   6. [1563. Stone Game V](https://leetcode.com/problems/stone-game-v/)`(Hard)`、[1563. 石子游戏 V](https://leetcode-cn.com/problems/stone-game-v/)`(困难)`
2. Triangulation，三角剖分
   1. [1039. Minimum Score Triangulation of Polygon](https://leetcode.com/problems/minimum-score-triangulation-of-polygon/)`(Medium)`、[1039. 多边形三角剖分的最低得分](https://leetcode-cn.com/problems/minimum-score-triangulation-of-polygon/)`(中等)`
3. Rectangle Segmentation，矩形分割
   1. [221. Maximal Square](https://leetcode.com/problems/maximal-square/)`(Medium)`、[221. 最大正方形](https://leetcode-cn.com/problems/maximal-square/)`(中等)`
   2. [1139. Largest 1-Bordered Square](https://leetcode.com/problems/largest-1-bordered-square/)`(Medium)`、[1139. 最大的以 1 为边界的正方形](https://leetcode-cn.com/problems/largest-1-bordered-square/)`(中等)`
   3. [1277. Count Square Submatrices with All Ones](https://leetcode.com/problems/count-square-submatrices-with-all-ones/)`(Medium)`、[1277. 统计全为 1 的正方形子矩阵](https://leetcode-cn.com/problems/count-square-submatrices-with-all-ones/)`(中等)`
   4. [85. Maximal Rectangle](https://leetcode.com/problems/maximal-rectangle/)`(Hard)`、[85. 最大矩形](https://leetcode-cn.com/problems/maximal-rectangle/)`(困难)`

## 12. Subsequence/Substring，子序列/子字符串

### 12.1. Longest Subsequence/Substring，最长子序列/子字符串

1. Longest Common Substring，最长公共子串
   1. [718. Maximum Length of Repeated Subarray](https://leetcode.com/problems/maximum-length-of-repeated-subarray/)`(Medium)`、[718. 最长重复子数组](https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/)`(中等)`
2. Longest Common Subsequence，最长公共子序列
   1. [1035. Uncrossed Lines](https://leetcode.com/problems/uncrossed-lines/)`(Medium)`、[1035. 不相交的线](https://leetcode-cn.com/problems/uncrossed-lines/)`(中等)`
   2. [1143. Longest Common Subsequence](https://leetcode.com/problems/longest-common-subsequence/)`(Medium)`、[1143. 最长公共子序列](https://leetcode-cn.com/problems/longest-common-subsequence/)`(中等)`
   3. [1458. Max Dot Product of Two Subsequences](https://leetcode.com/problems/max-dot-product-of-two-subsequences/)`(Hard)`、[1458. 两个子序列的最大点积](https://leetcode-cn.com/problems/max-dot-product-of-two-subsequences/)`(困难)`
3. Longest Increasing Subsequence，最长上升子序列
   1. [674. Longest Continuous Increasing Subsequence](https://leetcode.com/problems/longest-continuous-increasing-subsequence/)`(Easy)`、[674. 最长连续递增序列](https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence/)`(简单)`
   2. [300. Longest Increasing Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/)`(Medium)`、[300. 最长上升子序列](https://leetcode-cn.com/problems/longest-increasing-subsequence/)`(中等)`
   3. [673. Number of Longest Increasing Subsequence](https://leetcode.com/problems/number-of-longest-increasing-subsequence/)`(Medium)`、[673. 最长递增子序列的个数](https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence/)`(中等)`
   4. [354. Russian Doll Envelopes](https://leetcode.com/problems/russian-doll-envelopes/)`(Hard)`、[354. 俄罗斯套娃信封问题](https://leetcode-cn.com/problems/russian-doll-envelopes/)`(困难)`
   5. [1626. Best Team With No Conflicts](https://leetcode.com/problems/best-team-with-no-conflicts/)`(Hard)`、[1626. 无矛盾的最佳球队](https://leetcode-cn.com/problems/best-team-with-no-conflicts/)`(困难)`
4. Shortest Common Super-sequence，最短公共超级子序列
   1. [1092. Shortest Common Supersequence](https://leetcode.com/problems/shortest-common-supersequence/)`(Hard)`、[1092. 最短公共超序列](https://leetcode-cn.com/problems/shortest-common-supersequence/)`(困难)`
5. Others，其它
   1. [1218. Longest Arithmetic Subsequence of Given Difference](https://leetcode.com/problems/longest-arithmetic-subsequence-of-given-difference/)`(Medium)`、[1218. 最长定差子序列](https://leetcode-cn.com/problems/longest-arithmetic-subsequence-of-given-difference/)`(中等)`

### 12.2. Palindromic Subsequence/Substring，回文子序列/子字符串

1. Longest Palindromic Subsequence，最长回文子序列
   1. [516. Longest Palindromic Subsequence](https://leetcode.com/problems/longest-palindromic-subsequence/)`(Medium)`、[516. 最长回文子序列](https://leetcode-cn.com/problems/longest-palindromic-subsequence/)`(中等)`
2. Longest Palindromic Substring，最长回文子字符串
   1. [5. Longest Palindromic Substring](https://leetcode.com/problems/longest-palindromic-substring/)`(Medium)`、[5. 最长回文子串](https://leetcode-cn.com/problems/longest-palindromic-substring/)`(中等)`
3. Count Palindromic Subsequences/Substrings，回文子序列/子字符串的个数
   1. [647. Palindromic Substrings](https://leetcode.com/problems/palindromic-substrings/)`(Medium)`、[647. 回文子串](https://leetcode-cn.com/problems/palindromic-substrings/)`(中等)`
   2. [730. Count Different Palindromic Subsequences](https://leetcode.com/problems/count-different-palindromic-subsequences/)`(Hard)`、[730. 统计不同回文子字符串](https://leetcode-cn.com/problems/count-different-palindromic-subsequences/)`(困难)`
4. Palindromic Partitioning，回文分割
   1. [131. Palindrome Partitioning](https://leetcode.com/problems/palindrome-partitioning/)`(Medium)`、[131. 分割回文串](https://leetcode-cn.com/problems/palindrome-partitioning/)`(中等)`
   2. [132. Palindrome Partitioning II](https://leetcode.com/problems/palindrome-partitioning-ii/)`(Hard)`、[132. 分割回文串 II](https://leetcode-cn.com/problems/palindrome-partitioning-ii/)`(困难)`

## 13. String，字符串上的动态规划

### 13.1. String Transform，字符串变换

1. [583. Delete Operation for Two Strings](https://leetcode.com/problems/delete-operation-for-two-strings/)`(Medium)`、[583. 两个字符串的删除操作](https://leetcode-cn.com/problems/delete-operation-for-two-strings/)`(中等)`
2. [712. Minimum ASCII Delete Sum for Two Strings](https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/)`(Medium)`、[712. 两个字符串的最小 ASCII 删除和](https://leetcode-cn.com/problems/minimum-ascii-delete-sum-for-two-strings/)`(中等)`
3. [72. Edit Distance](https://leetcode.com/problems/edit-distance/)`(Hard)`、[72. 编辑距离](https://leetcode-cn.com/problems/edit-distance/)`(困难)`
4. [97. Interleaving String](https://leetcode.com/problems/interleaving-string/)`(Hard)`、[97. 交错字符串](https://leetcode-cn.com/problems/interleaving-string/)`(困难)`
5. [1312. Minimum Insertion Steps to Make a String Palindrome](https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome)`(Hard)`、[1312. 让字符串成为回文串的最少插入次数](https://leetcode-cn.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/)`(困难)`

### 13.2. Regular Expression Matching，正则表达式匹配

1. [678. Valid Parenthesis String](https://leetcode.com/problems/valid-parenthesis-string/)`(Medium)`、[678. 有效的括号字符串](https://leetcode-cn.com/problems/valid-parenthesis-string/)`(中等)`
2. [10. Regular Expression Matching](https://leetcode.com/problems/regular-expression-matching/)`(Hard)`、[10. 正则表达式匹配](https://leetcode-cn.com/problems/regular-expression-matching/)`(困难)`
3. [44. Wildcard Matching](https://leetcode.com/problems/wildcard-matching/)`(Hard)`、[44. 通配符匹配](https://leetcode-cn.com/problems/wildcard-matching/)`(困难)`
4. [639. Decode Ways II](https://leetcode.com/problems/decode-ways-ii/)`(Hard)`、[639. 解码方法 2](https://leetcode-cn.com/problems/decode-ways-ii/)`(困难)`

## 14. Multi-start state，多起始状态

1. [741. Cherry Pickup](https://leetcode.com/problems/cherry-pickup/)`(Hard)`、[741. 摘樱桃](https://leetcode-cn.com/problems/cherry-pickup/)`(困难)`
2. [1320. Minimum Distance to Type a Word Using Two Fingers](https://leetcode.com/problems/minimum-distance-to-type-a-word-using-two-fingers/)`(Hard)`、[1320. 二指输入的的最小距离](https://leetcode-cn.com/problems/minimum-distance-to-type-a-word-using-two-fingers/)`(困难)`
3. [1463. Cherry Pickup II](https://leetcode.com/problems/cherry-pickup-ii/)`(Hard)`、[1463. 摘樱桃 II](https://leetcode-cn.com/problems/cherry-pickup-ii/)`(困难)`

## 15. DP Optimizition，DP 优化

1. [837. New 21 Game](https://leetcode.com/problems/new-21-game/)`(Medium)`、[837. 新 21 点](https://leetcode-cn.com/problems/new-21-game/)`(中等)`
2. [1340. Jump Game V](https://leetcode.com/problems/jump-game-v/)`(Hard)`、[1340. 跳跃游戏 V](https://leetcode-cn.com/problems/jump-game-v/)`(困难)`
3. [1416. Restore The Array](https://leetcode.com/problems/restore-the-array/)`(Hard)`、[1416. 恢复数组](https://leetcode-cn.com/problems/restore-the-array/)`(困难)`
4. [1425. Constrained Subset Sum](https://leetcode.com/problems/constrained-subsequence-sum/)`(Hard)`、[1425. 带限制的子序列和](https://leetcode-cn.com/problems/constrained-subsequence-sum/)`(困难)`
5. [1434. Number of Ways to Wear Different Hats to Each Other](https://leetcode.com/problems/number-of-ways-to-wear-different-hats-to-each-other/)`(Hard)`、[1434. 每个人戴不同帽子的方案数](https://leetcode-cn.com/problems/number-of-ways-to-wear-different-hats-to-each-other/)`(困难)`
6. [1444. Number of Ways of Cutting a Pizza](https://leetcode.com/problems/number-of-ways-of-cutting-a-pizza/)`(Hard)`、[1444. 切披萨的方案数](https://leetcode-cn.com/problems/number-of-ways-of-cutting-a-pizza/)`(困难)`
7. [1621. Number of Sets of K Non-Overlapping Line Segments](https://leetcode.com/problems/number-of-sets-of-k-non-overlapping-line-segments/)`(Hard)`、[1621. 5527. 大小为 K 的不重叠线段的数目](https://leetcode-cn.com/problems/number-of-sets-of-k-non-overlapping-line-segments/)`(Hard)`

## 15. Bitmask DP，状态压缩 DP

1. [1125. Smallest Sufficient Team](https://leetcode.com/problems/smallest-sufficient-team/)`(Hard)`、[1125. 最小的必要团队](https://leetcode-cn.com/problems/smallest-sufficient-team/)`(困难)`
2. [1349. Maximum Students Taking Exam](https://leetcode.com/problems/maximum-students-taking-exam/)`(Hard)`、[1349. 参加考试的最大学生数](https://leetcode-cn.com/problems/maximum-students-taking-exam/)`(困难)`
3. [1655. Distribute Repeating Integers](https://leetcode.com/problems/maximum-students-taking-exam/)`(Hard)`、[1655. 分配重复整数](https://leetcode-cn.com/problems/distribute-repeating-integers/)`(困难)`

## 16. 轮廓线动态规划

1. [1659. Maximize Grid Happiness](https://leetcode.com/problems/maximum-students-taking-exam/)`(Hard)`、[1659. 最大化网格幸福感](https://leetcode-cn.com/problems/maximize-grid-happiness/)`(困难)`