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.

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(Easy)、118. 杨辉三角(简单)

  2. 119. Pascal's Triangle II(Easy)、119. 杨辉三角 II(简单)

  3. 64. Minimum Path Sum(Medium)、64. 最小路径和(中等)

  4. 120. Triangle(Medium)、120. 三角形最小路径和(中等)

  5. 931. Minimum Falling Path Sum(Medium)、931. 下降路径最小和(中等)

  6. 1289. Minimum Falling Path Sum II(hard)、1289. 下降路径最小和 II(困难)

  7. 1301. Number of Paths with Max Score(hard)、1301. 最大得分的路径数目(困难)

2. Fibonacci Numbers，斐波那契数列

  1. Fibonacci numbers，斐波那契数列问题

    1. 509. Fibonacci Number(Easy)、509. 斐波那契数(简单)

    2. 1137. N-th Tribonacci Number(Easy)、1137. 第 N 个泰波那契数(简单)

  2. Staircase，爬楼梯问题

    1. 70. Climbing Stairs(Easy)、70. 爬楼梯(简单)

    2. 746. Min Cost Climbing Stairs(Easy)、746. 使用最小花费爬楼梯(简单)

  3. House thief，偷房子问题

    1. 198. House Robber(Easy)、198. 打家劫舍(简单)

    2. 213. House Robber II(Medium)、213. 打家劫舍 II(中等)

3. Memory Search，记忆化搜索

  1. 139. Word BreakMedium、139. 单词拆分中等

  2. 140. Word Break IIHard、140. 单词拆分 II困难

  3. 329. 矩阵中的最长递增路径Hard、329. 矩阵中的最长递增路径困难

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

  1. Equal Subset Sum Partition，相等子集划分问题

    1. 416. Partition Equal Subset Sum(Medium)、416. 分割等和子集(中等)

  2. Subset Sum，子集和问题

    1. 494. Target Sum(Medium)、494. 目标和(中等)

  3. Minimum Subset Sum Difference，子集和的最小差问题

    1. 1049. Last Stone Weight II(Medium)、1049. 最后一块石头的重量 II(中等)

  4. Other，其它

    1. 474. Ones and Zeroes(Medium)、474. 一和零(中等)

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

  1. Coin Change，换硬币问题

    1. 322. Coin Change(Medium)、322. 零钱兑换(中等)

    2. 518. Coin Change 2(Medium)、518. 零钱兑换 II(中等)

  2. Others，其它

    1. 377. Combination Sum IV(Medium)、377. 组合总和 Ⅳ(中等)

    2. 638. Shopping Offers(Medium)、638. 大礼包(中等)

    3. 1449. Form Largest Integer With Digits That Add up to Target(Hard)、1449. 数位成本和为目标值的最大数字(困难)

6. Counting DP，计数 DP

  1. 62. Unique Paths(Medium)、62. 不同路径(中等)

  2. 63. Unique Paths II(Medium)、63. 不同路径 II(中等)

  3. 91. Decode Ways(Medium)、91. 解码方法(中等)

  4. 576. Out of Boundary Paths(Medium)、576. 出界的路径数(中等)

  5. 790. Domino and Tromino Tiling(Medium)、790. 多米诺和托米诺平铺(中等)

  6. 935. Knight Dialer(Medium)、935. 骑士拨号器(中等)

  7. 1155. Number of Dice Rolls With Target Sum(Medium)、1155. 掷骰子的 N 种方法(中等)

  8. 1641. Count Sorted Vowel Strings(Medium)、1641. 统计字典序元音字符串的数目(中等)

  9. 1220. Count Vowels Permutation(Hard)、1220. 统计元音字母序列的数目(困难)

  10. 1223. Dice Roll Simulation(Medium)、1223. 掷骰子模拟(中等)

  11. 552. Student Attendance Record II(Hard)、552. 学生出勤记录 II(困难)

  12. 1269. Number of Ways to Stay in the Same Place After Some Steps(Hard)、1269. 停在原地的方案数(困难)

  13. 1420. Build Array Where You Can Find The Maximum Exactly K Comparisons(Hard)、1420. 生成数组(困难)

  14. 1575. Count All Possible Routes(Hard)、1575. 统计所有可行路径(困难)

  15. 1639. Number of Ways to Form a Target String Given a Dictionary(Hard)、5542. 通过给定词典构造目标字符串的方案数(困难)

7. Probability DP，概率 DP

  1. 688. Knight Probability in Chessboard(Medium)、688-cn. “马”在棋盘上的概率(中等)

  2. 808. Soup Servings(Medium)、808. 分汤(中等)

8. Tree DP，树状 DP

  1. 96. Unique Binary Search Trees(Medium)、96. 不同的二叉搜索树(中等)

  2. 823. Binary Trees With Factors(Medium)、823. 带因子的二叉树(中等)

  3. 1130. Minimum Cost Tree From Leaf Values(Medium)、1130. 叶值的最小代价生成树(中等)

  4. 968. Binary Tree Cameras(Hard)、968. 监控二叉树(困难)

9. Optimal Solution，最优解问题

  1. Math，数学相关

    1. 279. Perfect Squares(Medium)、279. 完全平方数(中等)

    2. 368. Largest Divisible Subset(Medium)、368. 最大整除子集(中等)

    3. 646. Maximum Length of Pair Chain(Medium)、646. 最长数对链(中等)

    4. 650. 2 Keys Keyboard(Medium)、650. 只有两个键的键盘(中等)

    5. 801. Minimum Swaps To Make Sequences Increasing(Medium)、801. 使序列递增的最小交换次数(中等)

    6. 813. Largest Sum of Averages(Medium)、813. 最大平均值和的分组(中等)

    7. 1262. Greatest Sum Divisible by Three(Medium)、1262. 可被三整除的最大和(中等)

    8. 1537. Get the Maximum Score(Hard)、1537. 最大得分(困难)

  2. Buy and Sell Stock，股票买卖问题

    1. 309. Best Time to Buy and Sell Stock with Cooldown(Medium)、309. 最佳买卖股票时机含冷冻期(中等)

    2. 714. Best Time to Buy and Sell Stock with Transaction Fee(Medium)、714. 买卖股票的最佳时机含手续费(中等)

    3. 983. Minimum Cost For Tickets(Medium)、983. 最低票价(中等)

    4. 123. Best Time to Buy and Sell Stock III(Hard)、123. 买卖股票的最佳时机 III(困难)

    5. 188. Best Time to Buy and Sell Stock IV(Hard)、188. 买卖股票的最佳时机 IV(困难)

  3. Paint House，粉刷房子问题

    1. 256. Paint House(Easy)、256. 粉刷房子(简单)

    2. 265. Paint House II(Hard)、265. 粉刷房子 II(困难)

    3. 1473. Paint House III(Hard)、1473. 给房子涂色 III(困难)

  4. Job Schedule，工作计划问题

    1. 1235. Maximum Profit in Job Scheduling(Hard)、1235. 规划兼职工作(困难)

    2. 1335. Minimum Difficulty of a Job Schedule(Hard)、1335. 工作计划的最低难度(困难)

  5. Minimum Number of Operations，最少操作次数问题

    1. 1187. Make Array Strictly Increasing(Hard)、1187. 使数组严格递增(困难)

    2. 514. Freedom Trail(Hard)、514. 自由之路(困难)

10. Can I Win? 博弈 DP

  1. 292. Nim Game(Easy)、292. Nim 游戏(简单)

  2. 1025. Divisor Game(Easy)、1025. 除数博弈(简单)

  3. 464. Can I Win(Medium)、464. 我能赢吗(中等)

  4. 486. Predict the Winner(Medium)、486. 预测赢家(中等)

  5. 877. Stone Game(Medium)、877. 石子游戏(中等)

  6. 1140. Stone Game II(Medium)、1140. 石子游戏 II(中等)

  7. 1406. Stone Game III(Hard)、1406. 石子游戏 III(困难)

  8. 1510. Stone Game IV(Hard)、1510. 石子游戏 IV(困难)

11. Interval DP，区间 DP

  1. Intervals Merge，区间合并

    1. 312. Burst Balloons(Hard)、312. 戳气球(困难)

    2. 546. Remove Boxes(Hard)、546. 移除盒子(困难)

    3. 664. Strange Printer(Hard)、664. 奇怪的打印机(困难)

    4. 1478. Allocate Mailboxes(Hard)、1478. 安排邮筒(困难)

    5. 1547. Minimum Cost to Cut a Stick(Hard)、1547. 切棍子的最小成本(困难)

    6. 1563. Stone Game V(Hard)、1563. 石子游戏 V(困难)

  2. Triangulation，三角剖分

    1. 1039. Minimum Score Triangulation of Polygon(Medium)、1039. 多边形三角剖分的最低得分(中等)

  3. Rectangle Segmentation，矩形分割

    1. 221. Maximal Square(Medium)、221. 最大正方形(中等)

    2. 1139. Largest 1-Bordered Square(Medium)、1139. 最大的以 1 为边界的正方形(中等)

    3. 1277. Count Square Submatrices with All Ones(Medium)、1277. 统计全为 1 的正方形子矩阵(中等)

    4. 85. Maximal Rectangle(Hard)、85. 最大矩形(困难)

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

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

  1. Longest Common Substring，最长公共子串

    1. 718. Maximum Length of Repeated Subarray(Medium)、718. 最长重复子数组(中等)

  2. Longest Common Subsequence，最长公共子序列

    1. 1035. Uncrossed Lines(Medium)、1035. 不相交的线(中等)

    2. 1143. Longest Common Subsequence(Medium)、1143. 最长公共子序列(中等)

    3. 1458. Max Dot Product of Two Subsequences(Hard)、1458. 两个子序列的最大点积(困难)

  3. Longest Increasing Subsequence，最长上升子序列

    1. 674. Longest Continuous Increasing Subsequence(Easy)、674. 最长连续递增序列(简单)

    2. 300. Longest Increasing Subsequence(Medium)、300. 最长上升子序列(中等)

    3. 673. Number of Longest Increasing Subsequence(Medium)、673. 最长递增子序列的个数(中等)

    4. 354. Russian Doll Envelopes(Hard)、354. 俄罗斯套娃信封问题(困难)

    5. 1626. Best Team With No Conflicts(Hard)、1626. 无矛盾的最佳球队(困难)

  4. Shortest Common Super-sequence，最短公共超级子序列

    1. 1092. Shortest Common Supersequence(Hard)、1092. 最短公共超序列(困难)

  5. Others，其它

    1. 1218. Longest Arithmetic Subsequence of Given Difference(Medium)、1218. 最长定差子序列(中等)

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

  1. Longest Palindromic Subsequence，最长回文子序列

    1. 516. Longest Palindromic Subsequence(Medium)、516. 最长回文子序列(中等)

  2. Longest Palindromic Substring，最长回文子字符串

    1. 5. Longest Palindromic Substring(Medium)、5. 最长回文子串(中等)

  3. Count Palindromic Subsequences/Substrings，回文子序列/子字符串的个数

    1. 647. Palindromic Substrings(Medium)、647. 回文子串(中等)

    2. 730. Count Different Palindromic Subsequences(Hard)、730. 统计不同回文子字符串(困难)

  4. Palindromic Partitioning，回文分割

    1. 131. Palindrome Partitioning(Medium)、131. 分割回文串(中等)

    2. 132. Palindrome Partitioning II(Hard)、132. 分割回文串 II(困难)

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

13.1. String Transform，字符串变换

  1. 583. Delete Operation for Two Strings(Medium)、583. 两个字符串的删除操作(中等)

  2. 712. Minimum ASCII Delete Sum for Two Strings(Medium)、712. 两个字符串的最小 ASCII 删除和(中等)

  3. 72. Edit Distance(Hard)、72. 编辑距离(困难)

  4. 97. Interleaving String(Hard)、97. 交错字符串(困难)

  5. 1312. Minimum Insertion Steps to Make a String Palindrome(Hard)、1312. 让字符串成为回文串的最少插入次数(困难)

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

  1. 678. Valid Parenthesis String(Medium)、678. 有效的括号字符串(中等)

  2. 10. Regular Expression Matching(Hard)、10. 正则表达式匹配(困难)

  3. 44. Wildcard Matching(Hard)、44. 通配符匹配(困难)

  4. 639. Decode Ways II(Hard)、639. 解码方法 2(困难)

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

  1. 741. Cherry Pickup(Hard)、741. 摘樱桃(困难)

  2. 1320. Minimum Distance to Type a Word Using Two Fingers(Hard)、1320. 二指输入的的最小距离(困难)

  3. 1463. Cherry Pickup II(Hard)、1463. 摘樱桃 II(困难)

15. DP Optimizition，DP 优化

  1. 837. New 21 Game(Medium)、837. 新 21 点(中等)

  2. 1340. Jump Game V(Hard)、1340. 跳跃游戏 V(困难)

  3. 1416. Restore The Array(Hard)、1416. 恢复数组(困难)

  4. 1425. Constrained Subset Sum(Hard)、1425. 带限制的子序列和(困难)

  5. 1434. Number of Ways to Wear Different Hats to Each Other(Hard)、1434. 每个人戴不同帽子的方案数(困难)

  6. 1444. Number of Ways of Cutting a Pizza(Hard)、1444. 切披萨的方案数(困难)

  7. 1621. Number of Sets of K Non-Overlapping Line Segments(Hard)、1621. 5527. 大小为 K 的不重叠线段的数目(Hard)

15. Bitmask DP，状态压缩 DP

  1. 1125. Smallest Sufficient Team(Hard)、1125. 最小的必要团队(困难)

  2. 1349. Maximum Students Taking Exam(Hard)、1349. 参加考试的最大学生数(困难)

  3. 1655. Distribute Repeating Integers(Hard)、1655. 分配重复整数(困难)

16. 轮廓线动态规划

  1. 1659. Maximize Grid Happiness(Hard)、1659. 最大化网格幸福感(困难)

PreviousBacktrackingNextBinary search

Last updated