Problem List
§1.1 Climbing Stairs
- 70. Climbing Stairs
- 746. Min Cost Climbing Stairs
- 377. Combination Sum IV
- 2466. Count Ways to Build Good Strings
- 2266. Count Number of Texts
- 2533. Number of Good Binary Strings (Premium, similar to 2466)
§1.2 House Robber
- 198. House Robber
- 740. Delete and Earn
- 2320. Count Ways to Place Houses
- 213. House Robber II
- 3186. Maximum Total Damage by Spell
§1.3 Maximum Subarray Sum (Kadane's Algorithm)
- 53. Maximum Subarray
- 2606. Find Maximum Cost Substring
- 1749. Maximum Absolute Sum of Any Subarray
- 1191. K-Concatenation Maximum Sum
- 918. Maximum Sum Circular Subarray
- 2321. Concatenate Arrays for Maximum Score
- Related Problem:
- 152. Maximum Product Subarray
§2 Grid DP
§2.1 Basic Grid DP
- LCR 166. Maximum Value of Jewels
- 62. Unique Paths
- 63. Unique Paths II
- 64. Minimum Path Sum
- 120. Triangle Minimum Path Sum
- 931. Minimum Falling Path Sum
- 2684. Maximum Moves in a Matrix
- 2304. Minimum Path Cost in a Grid
- 1289. Minimum Falling Path Sum II
§2.2 Advanced Grid DP
- 1594. Maximum Non-Negative Product in Matrix
- 1301. Number of Paths with Maximum Score
- 2435. Paths Divisible by K in Matrix
- 174. Dungeon Game
- 329. Longest Increasing Path in a Matrix
- 2328. Number of Increasing Paths in a Grid
- 2267. Check Valid Parentheses Path
- 1937. Maximum Score with Deductions
- 1463. Cherry Pickup II
- 741. Cherry Pickup
§3 Knapsack Problems
§3.1 0-1 Knapsack (Items can be chosen only once)
- 2915. Longest Subsequence with Target Sum
- 416. Partition Equal Subset Sum
- 494. Target Sum
- 2787. Ways to Express a Number as Power Sum
- 3180. Maximum Reward with Operations
- 474. Ones and Zeroes (2D)
- 1049. Last Stone Weight II
- 1774. Closest Dessert Cost
- 879. Profitable Schemes
- 3082. Maximum Subsequence Energy Sum
- 956. Tallest Billboard
- 2518. Number of Good Partitions
- 2742. Minimum Cost to Paint Wall
- 2291. Maximum Stock Profit (Premium)
§3.2 Unbounded Knapsack (Items can be chosen multiple times)
- 322. Coin Change
- 518. Coin Change II
- 279. Perfect Squares
- 1449. Form Largest Integer with Digits Summing to Target
- 3183. Ways to Reach Target Sum (Hybrid Knapsack, Premium)
§3.3 Multiple Knapsack (Items can be chosen with a limit)
- 2585. Number of Ways to Obtain Score
- 3333. Initial Input String II
- 2902. Number of Restricted Subsets with Sum Constraint
§3.4 Group Knapsack
- 1155. Number of Dice Rolls with Target Sum
- 1981. Minimize Difference with Target Element
- 2218. Maximum Sum of K Coins from Piles
§4 Classic Linear DP
§4.1 Longest Common Subsequence (LCS)
- 1143. Longest Common Subsequence
- 583. Delete Operation for Two Strings
- 712. Minimum ASCII Delete Sum for Two Strings
- 72. Edit Distance
- 97. Interleaving String
- 115. Distinct Subsequences
- 1035. Uncrossed Lines
- 1458. Max Dot Product of Two Subsequences
- 1092. Shortest Common Supersequence
- 1639. Ways to Form Target String from Given Dictionary
- 44. Wildcard Matching
- 10. Regular Expression Matching
§4.2 Longest Increasing Subsequence (LIS)
- 300. Longest Increasing Subsequence
- 2826. Sort Three Groups
- 1964. Find Longest Valid Obstacle Course at Each Position
- 2111. Minimum Operations to Make Array K-Increasing
- 673. Number of Longest Increasing Subsequence
- 354. Russian Doll Envelopes
- 1691. Maximum Height by Stacking Cuboids
- 2407. Longest Increasing Subsequence II
- Related Problems:
- 368. Largest Divisible Subset
§5 State Machine DP
- 121. Best Time to Buy and Sell Stock (One Transaction)
- 122. Best Time to Buy and Sell Stock II (Unlimited Transactions)
- 123. Best Time to Buy and Sell Stock III (Two Transactions)
- 188. Best Time to Buy and Sell Stock IV (K Transactions)
- 309. Best Time to Buy and Sell Stock with Cooldown
- 714. Best Time to Buy and Sell Stock with Transaction Fee
§6 Partition DP
§6.1 Feasibility Partition
- 2369. Check Array Valid Partition
- 139. Word Break
§6.2 Optimal Partition
- 132. Palindrome Partitioning II
- 91. Decode Ways
- 639. Decode Ways II
- 1416. Restore the Array
§6.3 Fixed Partition Count
- 410. Split Array Largest Sum
- 1043. Partition Array for Maximum Sum
- 813. Largest Sum of Averages
- 1278. Palindrome Partitioning III
§6.4 Non-Overlapping Intervals
- 1235. Maximum Profit in Job Scheduling
- 1751. Maximum Number of Events That Can Be Attended II
§7 Classic DP Patterns
§7.1 One-Dimensional DP
- 2944. Minimum Gold Coins for Fruit Purchase
- 2140. Solving Intellectual Problem
- 983. Minimum Cost for Tickets
- 871. Minimum Refueling Stops
§7.2 Valid Subsequence DP
- 2501. Longest Square Wave in Array
- 1218. Longest Arithmetic Subsequence of Given Difference
- 1027. Longest Arithmetic Subsequence
- 873. Length of Longest Fibonacci Subsequence
§7.3 Fast Exponentiation for DP
- 70. Climbing Stairs
- 509. Fibonacci Number
- 1137. N-th Tribonacci Number
- 1220. Count Vowel Permutation
§7.4 Subrectangle DP
- 221. Maximal Square
- 1277. Count Square Submatrices with All Ones
§8 Interval DP
§8.1 Longest Palindromic Subsequence
- 516. Longest Palindromic Subsequence
- 730. Count Different Palindromic Subsequences
§8.2 Other Interval DP
- 5. Longest Palindromic Substring
- 375. Guess Number Higher or Lower II
§9 Bitmask DP (Subset DP)
§9.1 Permutation Type I (Independent Adjacent Elements)
- 526. Beautiful Arrangement
- 2850. Minimum Moves to Distribute Stones
§9.2 Permutation Type II (Dependent Adjacent Elements)
- 996. Number of Squareful Arrays
- 2741. Special Permutations
§9.3 Travelling Salesperson Problem (TSP)
- 943. Shortest Superstring
- 847. Shortest Path Visiting All Nodes
§10 Digit DP
- 2719. Count Integers
- 788. Rotated Digits
- 902. Numbers at Most N Given Digit Set
- 233. Number of Digit 1
- 600. Non-negative Integers without Consecutive Ones
- 1012. Numbers with Repeated Digits
§11 Data Structure Optimized DP
§11.1 Prefix Sum Optimized DP
- 2327. People Knowing the Secret
§11.2 Monotonic Stack Optimized DP
- 1335. Minimum Difficulty of a Job Schedule
§11.3 Monotonic Queue Optimized DP
- 1696. Jump Game VI
§11.4 Binary Indexed Tree/Segment Tree Optimized DP
- 2407. Longest Increasing Subsequence II
§12 Tree DP
§12.1 Tree Diameter
- 543. Diameter of Binary Tree
- 687. Longest Univalue Path
- 124. Binary Tree Maximum Path Sum
§12.2 Maximum Independent Set on Tree
- 337. House Robber III
§13 Graph DP
- 3243. Minimum Distance after Adding Roads I
- 787. Cheapest Flights within K Stops
- 1786. Restricted Paths from First Node to Last Node
§14 Game DP
- 1025. Divisor Game
- 877. Stone Game
- 486. Predict the Winner
§15 Probability/Expected Value DP
- 688. Knight Probability in Chessboard
- 837. New 21 Game
- 808. Soup Servings
Print Specific Solution
These problems require outputting one solution rather than all possible solutions, contrasting with backtracking problems.
- 368. Largest Divisible Subset
- 1449. Form Largest Integer With Digits That Add Up to Target (Lexicographical Order)
- 1092. Shortest Common Supersequence
- 943. Find the Shortest Superstring
- 1125. Smallest Sufficient Team
- 3260. Largest N-Digit K-Palindrome Number (Lexicographical Order)
- 3149. Lowest Score Permutation (Lexicographical Order)
- 656. Coin Path (Premium, Lexicographical Order)
- 471. Encode Shortest Length String (Premium)
Prefix and Suffix Decomposition
Some of these problems can also be solved using state machine DP.
- 42. Trapping Rain Water
- 123. Best Time to Buy and Sell Stock III (Split into two 121 problems)
- 1422. Maximum Score After Splitting a String
- 2256. Minimum Average Difference
- 1493. Longest Subarray of 1's After Deleting One Element
- 845. Longest Mountain in Array
- 2909. Minimum Mountain Triplet Sum
- 2483. Minimum Cost to Rearrange Shop
- 1525. Number of Good Ways to Split a String
- 2874. Maximum Value of Sorted Triplet
- 1031. Maximum Sum of Two Non-Overlapping Subarrays
- 689. Maximum Sum of Three Non-Overlapping Subarrays
- 2420. Find All Good Indices
- 2100. Find Good Picnic Days
- 926. Flip String to Monotone Increasing
- 334. Increasing Triplet Subsequence
- 2712. Minimum Cost to Make All Characters Equal
- 1653. Minimum Deletions to Make String Balanced
- 1186. Maximum Subarray Sum with One Deletion
- 1477. Find Two Non-Overlapping Subarrays with Target Sum
- 2680. Maximum OR Value
- 1671. Minimum Removals to Make Mountain Array
- 1888. Minimum Flips to Make Binary String Alternating
- 238. Product of Array Except Self
- 2906. Construct Product Matrix
- 3334. Array Maximum Factor Score
- 2167. Minimum Time to Remove All Blacklisted Cargo Wagons
- 2484. Count Palindromic Subsequences
- 2163. Minimize the Difference After Deleting Elements
- 2565. Minimum Score Subsequence
- 2552. Count Increasing Quadruplets
- 3302. Lexicographically Smallest Valid Sequence
- 3303. First Nearly Equal Substring Index
- 3287. Maximum Sequence Value in Array
- 3257. Maximum Sum of Values of Three Cars
- 3003. Maximum Partition Count After Operations
- 487. Max Consecutive Ones II (Premium)
- 1746. Maximum Subarray Sum After One Operation (Premium)
Transform X to Y
Some of these problems can also be solved with BFS.
- 397. Integer Replacement
- 2998. Minimum Operations to Make X and Y Equal
- 2059. Minimum Moves to Transform a Number
- 991. Broken Calculator
- 1553. Minimum Days to Eat N Oranges
Jump Game
A collection of variations on the jump game, which can sometimes be solved by different methods.
- 1306. Jump Game III
- 2770. Maximum Jumps to Reach the End
- 403. Frog Jump
- 1340. Jump Game V
- 1871. Jump Game VII
- 1696. Jump Game VI
- 975. Odd-Even Jump
- 1654. Minimum Jumps to Home
- LCP 09. Minimum Jump Count
- LCP 20. Fast Bus
- 656. Coin Path (Premium)
- 2297. Jump Game VIII (Premium)
Other Dynamic Programming Problems
These cover various concepts not easily grouped under one pattern.
- 823. Binary Trees with Factors
- 940. Distinct Subsequences II
- 135. Candy Distribution
- 650. 2 Keys Keyboard
- 638. Shopping Offers
- 467. Unique Substrings in Wraparound String
- 2262. Total Appeal of a String
- 828. Unique Letter Count in Substrings
- 2746. Modify and Append Letters to Form String
- 2930. Count Strings Containing Specific Substring
- 3041. Maximize Consecutive Elements After Modification
- 1569. Rearrange Subarrays to Form BST
- 818. Race Car
- 920. Number of Music Playlists
- 1388. Pizza With 3n Slices
- 1987. Distinct Good Subsequences
- 903. Valid Permutations for DI Sequence
- 2272. Substring with Maximum Fluctuation
- 1896. Minimum Operations to Flip Expression
- 1531. Compress String with Minimum Length II
- 964. Minimum Operations to Represent a Number
- 1787. Make XOR of All Subarrays Equal to Zero
- 2060. Check Homomorphic Strings
- 2809. Min Time to Make Array Sum ≤ X
- LCP 14. Array Segmentation
- LCP 36. Max Number of Card Groups
- LCP 38. Guarding the Castle
- LCP 43. Traffic at Crossroads
- LCP 65. Comfortable Humidity
- 3299. Sum of Consecutive Subsequences (Premium)
- 2189. Number of Ways to Build Card Houses (Premium)
- 2597. Number of Beautiful Subsets
- 2638. Count K-Free Subsets (Premium)
https://leetcode.cn/circle/discuss/tXLS3i/