Dynamic Programming
133 problems · 86 with full explanations
7 Easy59 Medium18 Hard
Dynamic programming solves problems by breaking them into overlapping sub-problems and storing results to avoid redundant work. The key steps are: define state, write a recurrence relation, set base cases, and choose top-down (memoization) or bottom-up (tabulation). DP often yields O(n²) → O(n) time improvements over brute force.
How to practice
To practice Dynamic Programming problems effectively, start with the Easy problems listed below, trace through each solution on paper, then re-implement without looking. When you can recognise the dynamic programming pattern within 30 seconds of reading a new problem, move on to Medium difficulty. Use the related topic pages and our study guide for a structured progression.
Start here (Easy + explained)
All Dynamic Programming problems
- 22.Generate ParenthesesMedium
- 32.Longest Valid ParenthesesHard
- 44.Wildcard MatchingHard
- 63.Unique Paths IIMedium
- 70.Climbing StairsEasy
- 85.Maximal RectangleHard
- 87.Scramble StringHard
- 95.Unique Binary Search Trees IIMedium
- 118.Pascal's TriangleEasy
- 120.TriangleMedium
- 122.Best Time to Buy and Sell Stock IIMedium
- 174.Dungeon GameHard
- 198.House RobberMedium
- 213.House Robber IIMedium
- 221.Maximal SquareMedium
- 241.Different Ways to Add ParenthesesMedium
- 264.Ugly Number IIMedium
- 309.Best Time to Buy and Sell Stock with CooldownMedium
- 329.Longest Increasing Path in a MatrixHard
- 368.Largest Divisible SubsetMedium
- 416.Partition Equal Subset SumMedium
- 467.Unique Substrings in Wraparound StringMedium
- 474.Ones and ZeroesMedium
- 494.Target SumMedium
- 600.Non-negative Integers without Consecutive OnesHard
- 646.Maximum Length of Pair ChainMedium
- 650.2 Keys KeyboardMedium
- 664.Strange PrinterHard
- 678.Valid Parenthesis StringMedium
- 696.Count Binary SubstringsEasy
- 712.Minimum ASCII Delete Sum for Two StringsMedium
- 790.Domino and Tromino TilingMedium
- 799.Champagne TowerMedium
- 808.Soup ServingsUnknown
- 818.Race CarUnknown
- 837.New 21 GameMedium
- 838.Push DominoesMedium
- 873.Length of Longest Fibonacci SubsequenceMedium
- 898.Bitwise ORs of SubarraysMedium
- 902.Numbers At Most N Given Digit SetHard
- 960.Delete Columns to Make Sorted IIIHard
- 983.Minimum Cost For TicketsMedium
- 1000.Minimum Cost to Merge StonesHard
- 1014.Best Sightseeing PairMedium
- 1039.Minimum Score Triangulation of PolygonMedium
- 1079.Letter Tile PossibilitiesMedium
- 1092.Shortest Common SupersequenceHard
- 1105.Filling Bookcase ShelvesMedium
- 1140.Stone Game IIMedium
- 1262.Greatest Sum Divisible by ThreeMedium
- 1277.Count Square Submatrices with All OnesMedium
- 1395.Count Number of TeamsUnknown
- 1411.Number of Ways to Paint N × 3 GridUnknown
- 1458.Max Dot Product of Two SubsequencesMedium
- 1493.Longest Subarray of 1's After Deleting One ElementMedium
- 1504.Count Submatrices With All OnesUnknown
- 1513.Number of Substrings With Only 1sUnknown
- 1514.Path with Maximum ProbabilityMedium
- 1578.Minimum Time to Make Rope ColorfulMedium
- 1611.Minimum One Bit Operations to Make Integers ZeroUnknown
- 1621.Number of Sets of K Non-Overlapping Line SegmentsUnknown
- 1639.Number of Ways to Form a Target String Given a DictionaryHard
- 1653.Minimum Deletions to Make String BalancedMedium
- 1671.Minimum Number of Removals to Make Mountain ArrayHard
- 1749.Maximum Absolute Sum of Any SubarrayMedium
- 1751.Maximum Number of Events That Can Be Attended IIUnknown
- 1799.Maximize Score After N OperationsUnknown
- 1857.Largest Color Value in a Directed GraphHard
- 1862.Sum of Floored PairsUnknown
- 1900.The Earliest and Latest Rounds Where Players CompeteUnknown
- 1911.Maximum Alternating Subsequence SumUnknown
- 1931.Painting a Grid With Three Different ColorsUnknown
- 1937.Maximum Number of Points with CostUnknown
- 1976.Number of Ways to Arrive at DestinationMedium
- 1994.The Number of Good SubsetsUnknown
- 2008.Maximum Earnings From TaxiUnknown
- 2054.Two Best Non-Overlapping EventsUnknown
- 2110.Number of Smooth Descent Periods of a StockMedium
- 2140.Solving Questions With BrainpowerMedium
- 2147.Number of Ways to Divide a Long CorridorUnknown
- 2163.Minimum Difference in Sums After Removal of ElementsUnknown
- 2311.Longest Binary Subsequence Less Than or Equal to KMedium
- 2327.Number of People Aware of a SecretUnknown
- 2338.Count the Number of Ideal ArraysMedium
- 2369.Check if There is a Valid Partition For The ArrayMedium
- 2370.Longest Ideal SubsequenceMedium
- 2400.Number of Ways to Reach a Position After Exactly k StepsMedium
- 2435.Paths in Matrix Whose Sum Is Divisible by KHard
- 2463.Minimum Total Distance TraveledHard
- 2466.Count Ways To Build Good StringsMedium
- 2501.Longest Square Streak in an ArrayMedium
- 2572.Count the Number of Square-Free SubsetsUnknown
- 2573.Find the String with LCPUnknown
- 2684.Maximum Number of Moves in a GridMedium
- 2707.Extra Characters in a StringMedium
- 2787.Ways to Express an Integer as Sum of PowersUnknown
- 2818.Apply Operations to Maximize ScoreUnknown
- 2872.Maximum Number of K-Divisible ComponentsUnknown
- 2900.Longest Unequal Adjacent Groups Subsequence IEasy
- 2901.Longest Unequal Adjacent Groups Subsequence IIUnknown
- 2916.Subarrays Distinct Element Sum of Squares IIUnknown
- 2930.Number of Strings Which Can Be Rearranged to Contain SubstringMedium
- 2976.Minimum Cost to Convert String IMedium
- 2977.Minimum Cost to Convert String IIUnknown
- 2999.Count the Number of Powerful IntegersUnknown
- 3003.Maximize the Number of Partitions After OperationsUnknown
- 3068.Find the Maximum Sum of Node ValuesHard
- 3122.Minimum Number of Operations to Satisfy ConditionsUnknown
- 3129.Find All Possible Stable Binary Arrays IUnknown
- 3130.Find All Possible Stable Binary Arrays IIUnknown
- 3147.Taking Maximum Energy From the Mystic DungeonUnknown
- 3149.Find the Minimum Cost Array PermutationMedium
- 3186.Maximum Total Damage With Spell CastingMedium
- 3192.Minimum Operations to Make Binary Array Elements Equal to One IIEasy
- 3201.Find the Maximum Length of Valid Subsequence IEasy
- 3202.Find the Maximum Length of Valid Subsequence IIUnknown
- 3333.Find the Original Typed String IIUnknown
- 3335.Total Characters in String After Transformations IMedium
- 3337.Total Characters in String After Transformations IIUnknown
- 3343.Count Number of Balanced PermutationsUnknown
- 3363.Find the Maximum Number of Fruits CollectedUnknown
- 3418.Maximum Amount of Money Robot Can EarnMedium
- 3459.Length of Longest V-Shaped Diagonal SegmentEasy
- 3487.Maximum Unique Subarray Sum After DeletionMedium
- 3539.Find Sum of Array Product of Magical SequencesUnknown
- 3562.Maximum Profit from Trading Stocks with DiscountsUnknown
- 3573.Best Time to Buy and Sell Stock VUnknown
- 3578.Count Partitions With Max-Min Difference at Most KUnknown
- 3640.Trionic Array IIUnknown
- 3643.Flip Square Submatrix VerticallyUnknown
- 3651.Minimum Cost Path with TeleportationsUnknown
- 3652.Best Time to Buy and Sell Stock using StrategyUnknown
- 3721.Longest Balanced Subarray IIUnknown