Skip to content

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

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/