leetcode动态规划题目总结

ref :https://leetcode.cn/circle/article/2Xxlw3/

这是一篇我在leetcode.com上撰写的文章Dynamic Programming Summary，就不翻回中文了，直接copy过来了。

Hello everyone, I am a Chinese noob programmer. I have practiced questions on leetcode.com for 2 years. During this time, I studied a lot from many Great Gods' articles. After worship, I always wanted to write an article as they did, and now I take the courage to write my first article here.

This is an article summarizing topics related to dynamic programming. Its main inspiration comes from these two articles: Dynamic Programming Patterns and 怎样学好动态规划？ - 穷码农的回答 - 知乎. DP is always a very difficult problem for me and lately, I have done dozens of questions to improve my DP skills. But the DP problem is so flexible that random practice has little effect. Therefore, I made further improvements based on these two articles and summarize some typical topics of DP problem. I hope this article can help you.

In this article, all problems come from leetcode.com and leetcode.cn which is a Chinese version of leetcode.com. By the way, because I am Chinese, I attached the Chinese translation after the English topics so that I can use this article more convenient in the future. Moreover, can anyone tell me how to create a table of contents? I wrote this article with VSCode and attempted many extensions to do this but all of them failed. I will be very grateful if you can tell me a way to achieve this function.

I will continue practicing DP problems on leetcode.com and will keep updating this article. If you have any better suggestions or supplements, welcome to put them in the comment area and @me. Now the main text begins.

1. Number Tower，数塔

• 118. Pascal's Triangle(Easy)、118. 杨辉三角(简单)
• 119. Pascal's Triangle II(Easy)、119. 杨辉三角 II(简单)
• 64. Minimum Path Sum(Medium)、64. 最小路径和(中等)
• 120. Triangle(Medium)、120. 三角形最小路径和(中等)
• 931. Minimum Falling Path Sum(Medium)、931. 下降路径最小和(中等)
• 1289. Minimum Falling Path Sum II(hard)、1289. 下降路径最小和 II(困难)
• 1301. Number of Paths with Max Score(hard)、1301. 最大得分的路径数目(困难)

2. Fibonacci Numbers，斐波那契数列

2.1 Fibonacci numbers，斐波那契数列问题

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

2.2 Staircase，爬楼梯问题

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

2.3 House thief，偷房子问题

• 198. House Robber(Easy)、198. 打家劫舍(简单)
• 213. House Robber II(Medium)、213. 打家劫舍 II(中等)

3. Memory Search，记忆化搜索

• 139. Word BreakMedium、139. 单词拆分中等
• 140. Word Break IIHard、140. 单词拆分 II困难
• 329. Longest Increasing Path in a MatrixHard、329. 矩阵中的最长递增路径困难
• 1857. Largest Color Value in a Directed GraphHard、1857. 有向图中最大颜色值困难

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

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

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

4.2  Subset Sum，子集和问题

• 494. Target Sum(Medium)、494. 目标和(中等)
• Minimum Subset Sum Difference，子集和的最小差问题
• 1049. Last Stone Weight II(Medium)、1049. 最后一块石头的重量 II(中等)

4.3  Other，其它

• 474. Ones and Zeroes(Medium)、474. 一和零(中等)
• 1770. Maximum Score from Performing Multiplication Operations(Medium)、1770. 执行乘法运算的最大分数(中等)
• 956. Tallest Billboard(Hard)、956. 最高的广告牌(困难)
• 1751. Maximum Number of Events That Can Be Attended II(Hard)、1751. 最多可以参加的会议数目 II(困难)
• 2218. Maximum Value of K Coins From Piles(Hard)、2218. 从栈中取出 K 个硬币的最大面值和(困难)

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

5. 1  Coin Change，换硬币问题

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

5.2 Others，其它

• 377. Combination Sum IV(Medium)、377. 组合总和 Ⅳ(中等)
• 638. Shopping Offers(Medium)、638. 大礼包(中等)
• 1449. Form Largest Integer With Digits That Add up to Target(Hard)、1449. 数位成本和为目标值的最大数字(困难)
• 2188. Minimum Time to Finish the Race(Hard)、2188. 完成比赛的最少时间(困难)

6. Counting DP，计数 DP

• 62. Unique Paths(Medium)、62. 不同路径(中等)
• 63. Unique Paths II(Medium)、63. 不同路径 II(中等)
• 91. Decode Ways(Medium)、91. 解码方法(中等)
• 576. Out of Boundary Paths(Medium)、576. 出界的路径数(中等)
• 790. Domino and Tromino Tiling(Medium)、790. 多米诺和托米诺平铺(中等)
• 935. Knight Dialer(Medium)、935. 骑士拨号器(中等)
• 1155. Number of Dice Rolls With Target Sum(Medium)、1155. 掷骰子的 N 种方法(中等)
• 1641. Count Sorted Vowel Strings(Medium)、1641. 统计字典序元音字符串的数目(中等)
• 2320. Count Number of Ways to Place Houses(Medium)、2320. 统计放置房子的方式数(中等)
• 1220. Count Vowels Permutation(Hard)、1220. 统计元音字母序列的数目(困难)
• 1223. Dice Roll Simulation(Medium)、1223. 掷骰子模拟(中等)
• 552. Student Attendance Record II(Hard)、552. 学生出勤记录 II(困难)
• 1269. Number of Ways to Stay in the Same Place After Some Steps(Hard)、1269. 停在原地的方案数(困难)
• 1420. Build Array Where You Can Find The Maximum Exactly K Comparisons(Hard)、1420. 生成数组(困难)
• 1575. Count All Possible Routes(Hard)、1575. 统计所有可行路径(困难)
• 1639. Number of Ways to Form a Target String Given a Dictionary(Hard)、5542. 通过给定词典构造目标字符串的方案数(困难)
• 1866. Number of Ways to Rearrange Sticks With K Sticks Visible(Hard)、1866. 恰有 K 根木棍可以看到的排列数目(困难)
• 1955. Count Number of Special Subsequences(Hard)、1955. 统计特殊子序列的数目(困难)
• 1977. Number of Ways to Separate Numbers(Hard)、1977. 划分数字的方案数(困难)
• 2318. Number of Distinct Roll Sequences(Hard)、2318. 不同骰子序列的数目(困难)

7. Probability DP，概率 DP

• 688. Knight Probability in Chessboard(Medium)、688-cn. “马”在棋盘上的概率(中等)
• 808. Soup Servings(Medium)、808. 分汤(中等)

8. Tree DP，树状 DP

• 96. Unique Binary Search Trees(Medium)、96. 不同的二叉搜索树(中等)
• 823. Binary Trees With Factors(Medium)、823. 带因子的二叉树(中等)
• 1130. Minimum Cost Tree From Leaf Values(Medium)、1130. 叶值的最小代价生成树(中等)
• 968. Binary Tree Cameras(Hard)、968. 监控二叉树(困难)
• 1916. Count Ways to Build Rooms in an Ant Colony(Hard)、1916. 统计为蚁群构筑房间的不同顺序(困难)

9. Optimal Solution，最优解问题

9.1  Math，数学相关

• 279. Perfect Squares(Medium)、279. 完全平方数(中等)
• 368. Largest Divisible Subset(Medium)、368. 最大整除子集(中等)
• 646. Maximum Length of Pair Chain(Medium)、646. 最长数对链(中等)
• 650. 2 Keys Keyboard(Medium)、650. 只有两个键的键盘(中等)
• 801. Minimum Swaps To Make Sequences Increasing(Medium)、801. 使序列递增的最小交换次数(中等)
• 813. Largest Sum of Averages(Medium)、813. 最大平均值和的分组(中等)
• 1262. Greatest Sum Divisible by Three(Medium)、1262. 可被三整除的最大和(中等)
• 1537. Get the Maximum Score(Hard)、1537. 最大得分(困难)

9.2  Buy and Sell Stock，股票买卖问题

• 309. Best Time to Buy and Sell Stock with Cooldown(Medium)、309. 最佳买卖股票时机含冷冻期(中等)
• 714. Best Time to Buy and Sell Stock with Transaction Fee(Medium)、714. 买卖股票的最佳时机含手续费(中等)
• 983. Minimum Cost For Tickets(Medium)、983. 最低票价(中等)
• 2008. Maximum Earnings From Taxi(Medium)、2008. 出租车的最大盈利(中等)
• 123. Best Time to Buy and Sell Stock III(Hard)、123. 买卖股票的最佳时机 III(困难)
• 188. Best Time to Buy and Sell Stock IV(Hard)、188. 买卖股票的最佳时机 IV(困难)

9.3   Paint House，粉刷房子问题

• 256. Paint House(Easy)、256. 粉刷房子(简单)
• 265. Paint House II(Hard)、265. 粉刷房子 II(困难)
• 1473. Paint House III(Hard)、1473. 给房子涂色 III(困难)

9.4  Job Schedule，工作计划问题

• 1235. Maximum Profit in Job Scheduling(Hard)、1235. 规划兼职工作(困难)
• 1335. Minimum Difficulty of a Job Schedule(Hard)、1335. 工作计划的最低难度(困难)
• Minimum Number of Operations，最少操作次数问题
• 1824. Minimum Sideway Jumps(Medium)、1824. 最少侧跳次数(中等)
• 1187. Make Array Strictly Increasing(Hard)、1187. 使数组严格递增(困难)
• 514. Freedom Trail(Hard)、514. 自由之路(困难)
• 1787. Make the XOR of All Segments Equal to Zero(Hard)、1787. 使所有区间的异或结果为零(困难)
• 1883. Minimum Skips to Arrive at Meeting On Time(Hard)、1883. 准时抵达会议现场的最小跳过休息次数(困难)
• 2209. Minimum White Tiles After Covering With Carpets(Hard)、2209. 用地毯覆盖后的最少白色砖块(困难)

9.5  Others，其它

• 1959. Minimum Total Space Wasted With K Resizing Operations(Medium)、1959. K 次调整数组大小浪费的最小总空间(中等)
• 2140. Solving Questions With Brainpower(Medium)、2140. 解决智力问题(中等)

10. Can I Win? 博弈 DP

• 292. Nim Game(Easy)、292. Nim 游戏(简单)
• 1025. Divisor Game(Easy)、1025. 除数博弈(简单)
• 464. Can I Win(Medium)、464. 我能赢吗(中等)
• 486. Predict the Winner(Medium)、486. 预测赢家(中等)
• 877. Stone Game(Medium)、877. 石子游戏(中等)
• 1140. Stone Game II(Medium)、1140. 石子游戏 II(中等)
• 1406. Stone Game III(Hard)、1406. 石子游戏 III(困难)
• 1510. Stone Game IV(Hard)、1510. 石子游戏 IV(困难)
• 1872. Stone Game VIII(Hard)、1872. 石子游戏 VIII(困难)

11. Interval DP，区间 DP

11.1   Intervals Merge，区间合并

• 312. Burst Balloons(Hard)、312. 戳气球(困难)
• 546. Remove Boxes(Hard)、546. 移除盒子(困难)
• 664. Strange Printer(Hard)、664. 奇怪的打印机(困难)
• 1478. Allocate Mailboxes(Hard)、1478. 安排邮筒(困难)
• 1547. Minimum Cost to Cut a Stick(Hard)、1547. 切棍子的最小成本(困难)
• 1563. Stone Game V(Hard)、1563. 石子游戏 V(困难)
• 2019. The Score of Students Solving Math Expression(Hard)、2019. 解出数学表达式的学生分数(困难)

11.2  Triangulation，三角剖分

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

11.3   Rectangle Segmentation，矩形分割

• 221. Maximal Square(Medium)、221. 最大正方形(中等)
• 1139. Largest 1-Bordered Square(Medium)、1139. 最大的以 1 为边界的正方形(中等)
• 1277. Count Square Submatrices with All Ones(Medium)、1277. 统计全为 1 的正方形子矩阵(中等)
• 85. Maximal Rectangle(Hard)、85. 最大矩形(困难)
• 2088. Count Fertile Pyramids in a Land(Hard)、2088. 统计农场中肥沃金字塔的数目(困难)

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

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

• Longest Common Substring，最长公共子串
• 718. Maximum Length of Repeated Subarray(Medium)、718. 最长重复子数组(中等)

12.2   Longest Common Subsequence，最长公共子序列

• 1035. Uncrossed Lines(Medium)、1035. 不相交的线(中等)
• 1143. Longest Common Subsequence(Medium)、1143. 最长公共子序列(中等)
• 1458. Max Dot Product of Two Subsequences(Hard)、1458. 两个子序列的最大点积(困难)

12.3   Longest Increasing Subsequence，最长上升子序列

• 674. Longest Continuous Increasing Subsequence(Easy)、674. 最长连续递增序列(简单)
• 300. Longest Increasing Subsequence(Medium)、300. 最长上升子序列(中等)
• 673. Number of Longest Increasing Subsequence(Medium)、673. 最长递增子序列的个数(中等)
• 354. Russian Doll Envelopes(Hard)、354. 俄罗斯套娃信封问题(困难)
• 1626. Best Team With No Conflicts(Hard)、1626. 无矛盾的最佳球队(困难)
• 1964. Find the Longest Valid Obstacle Course at Each Position(Hard)、1964. 找出到每个位置为止最长的有效障碍赛跑路线(困难)
• 2111. Minimum Operations to Make the Array K-Increasing(Hard)、2111. 使数组 K 递增的最少操作次数(困难)

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

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

12.5   Others，其它

• 1218. Longest Arithmetic Subsequence of Given Difference(Medium)、1218. 最长定差子序列(中等)
• 1911. Maximum Alternating Subsequence Sum(Medium)、1911. 最大子序列交替和(中等)
• 943. Find the Shortest Superstring(Hard)、943. 最短超级串(困难)
• 12.2. Palindromic Subsequence/Substring，回文子序列/子字符串

12.6   Longest Palindromic Subsequence，最长回文子序列

• 516. Longest Palindromic Subsequence(Medium)、516. 最长回文子序列(中等)
• 1771. Maximize Palindrome Length From Subsequences(Hard)、1771. 由子序列构造的最长回文串的长度(困难)

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

• 5. Longest Palindromic Substring(Medium)、5. 最长回文子串(中等)
• Count Palindromic Subsequences/Substrings，回文子序列/子字符串的个数
• 647. Palindromic Substrings(Medium)、647. 回文子串(中等)
• 730. Count Different Palindromic Subsequences(Hard)、730. 统计不同回文子字符串(困难)

12.8   Palindromic Partitioning，回文分割

• 131. Palindrome Partitioning(Medium)、131. 分割回文串(中等)
• 132. Palindrome Partitioning II(Hard)、132. 分割回文串 II(困难)
• 1278. Palindrome Partitioning III(Hard)、1278. 分割回文串 III(困难)
• 1745. Palindrome Partitioning IV(Hard)、1745. 回文串分割 IV(困难)

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

13.1. String Transform，字符串变换

• 583. Delete Operation for Two Strings(Medium)、583. 两个字符串的删除操作(中等)
• 712. Minimum ASCII Delete Sum for Two Strings(Medium)、712. 两个字符串的最小 ASCII 删除和(中等)
• 72. Edit Distance(Hard)、72. 编辑距离(困难)
• 97. Interleaving String(Hard)、97. 交错字符串(困难)
• 1312. Minimum Insertion Steps to Make a String Palindrome(Hard)、1312. 让字符串成为回文串的最少插入次数(困难)

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

• 678. Valid Parenthesis String(Medium)、678. 有效的括号字符串(中等)
• 10. Regular Expression Matching(Hard)、10. 正则表达式匹配(困难)
• 44. Wildcard Matching(Hard)、44. 通配符匹配(困难)
• 639. Decode Ways II(Hard)、639. 解码方法 2(困难)

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

• 741. Cherry Pickup(Hard)、741. 摘樱桃(困难)
• 1320. Minimum Distance to Type a Word Using Two Fingers(Hard)、1320. 二指输入的的最小距离(困难)
• 1463. Cherry Pickup II(Hard)、1463. 摘樱桃 II(困难)

15. DP Optimizition，DP 优化

• 837. New 21 Game(Medium)、837. 新 21 点(中等)
• 1937. Maximum Number of Points with Cost(Medium)、1937. 扣分后的最大得分(中等)
• 1340. Jump Game V(Hard)、1340. 跳跃游戏 V(困难)
• 1696. Jump Game VI(Medium)、1696. 跳跃游戏 VI(中等)
• 1416. Restore The Array(Hard)、1416. 恢复数组(困难)
• 1425. Constrained Subset Sum(Hard)、1425. 带限制的子序列和(困难)
• 1434. Number of Ways to Wear Different Hats to Each Other(Hard)、1434. 每个人戴不同帽子的方案数(困难)
• 1444. Number of Ways of Cutting a Pizza(Hard)、1444. 切披萨的方案数(困难)
• 1621. Number of Sets of K Non-Overlapping Line Segments(Hard)、1621. 大小为 K 的不重叠线段的数目(困难)

15. Bitmask DP，状态压缩 DP

• 1947. Maximum Compatibility Score Sum(Medium)、1947. 最大兼容性评分和(中等)
• 1125. Smallest Sufficient Team(Hard)、1125. 最小的必要团队(困难)
• 1349. Maximum Students Taking Exam(Hard)、1349. 参加考试的最大学生数(困难)
• 1655. Distribute Repeating Integers(Hard)、1655. 分配重复整数(困难)
• 1799. Maximize Score After N Operations(Hard)、1799. N 次操作后的最大分数和(困难)
• 1815. Maximum Number of Groups Getting Fresh Donuts(Hard)、1815. 得到新鲜甜甜圈的最多组数(困难)
• 1879. Minimum XOR Sum of Two Arrays(Hard)、1879. 两个数组最小的异或值之和(困难)
• 1900. The Earliest and Latest Rounds Where Players Compete(Hard)、1900. 最佳运动员的比拼回合(困难)
• 2172. Maximum AND Sum of Array(Hard)、2172. 数组的最大与和(困难)

16. 轮廓线动态规划

• 1659. Maximize Grid Happiness(Hard)、1659. 最大化网格幸福感(困难)
• 1931. Painting a Grid With Three Different Colors(Hard)、1931. 用三种不同颜色为网格涂色(困难)

Thanks for your browsing and best wishes to you.