Dynamic Programming Coding Problems: 402 Questions with Solutions
402 dynamic programming coding problems — 11 easy · 208 medium · 183 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 8-day plan.
- Problems: 402
- By difficulty: 11 easy · 208 medium · 183 hard
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
- Cost: Free on every plan; sign in to run and submit
Dynamic programming solves a problem by solving its smaller versions once each and remembering the answers. The problems here run from the one-dimensional cases (climbing stairs, house robber, the best subarray) to two-dimensional tables over strings and grids, and the skill is the same each time: name the state, write the recurrence, decide the order that makes every dependency ready before it is needed, then shrink the table to what the recurrence actually reads.
New to dynamic programming? Read the Dynamic Programming tutorial first.
How dynamic programming works, step by step
nums = [2, 7, 9, 3, 1]- No two neighbouring houses can both be robbed. Let dp[i] be the most money from houses 0..i: either skip house i and keep dp[i−1], or rob it and add nums[i] to dp[i−2], the best that leaves house i−1 alone.
- dp[0] = 2: with a single house, rob it. This is the base case every later cell builds on.
- dp[1] = max(dp[0], nums[1]) = max(2, 7) = 7: houses 0 and 1 are neighbours, so take the richer one, house 1.
- dp[2] = max(skip: 7, rob: 2 + 9 = 11) = 11. Robbing house 2 wins, so the best plan so far ends with house 2.
- dp[3] = max(skip: 11, rob: 7 + 3 = 10) = 11. Skipping wins: house 3 is worth less than what robbing it would give up.
- dp[4] = max(skip: 11, rob: 11 + 1 = 12) = 12. Robbing house 4 wins, so the best plan so far ends with house 4.
- The answer is dp[4] = 12. Walking back, a house was robbed wherever dp changes from its left neighbour: houses 0, 2 and 4, 2 + 9 + 1 = 12. One pass, O(n) time, and O(1) space keeping only the last two cells.
Dynamic Programming study plan
14 of the 402 Dynamic Programming problems (4 easy, 7 medium and 3 hard) over 8 days, about 8 h 10 min in all — the pattern first, then easiest to hardest. After that, the other 388 in the full list below are practice at your own pace. Then move on to Memoization.
Day 1
Learn the pattern: read the essentials and step through the walkthrough above, then solve these 3.
- Best Time to Buy and Sell Stock Easy
- Is Subsequence Easy
- Counting Bits Easy
Day 2
Medium problems: the same pattern with one twist each. Name the twist before you code.
- Climbing Stairs Easy
- Maximum Subarray Medium
Day 3
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
- Longest Palindromic Substring Medium
- Jump Game Medium
Day 4
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
- Ugly Number II Medium
- Generate Parentheses Medium
Day 5
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
- Target Sum Medium
- Cheapest Flights Within K Stops Medium
Day 6
Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.
- Trapping Rain Water Hard
Day 7
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
Day 8
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
Dynamic Programming: the essentials
When to reach for it
The question asks for a count of ways, a minimum or maximum cost, or whether something is achievable — and a choice made now changes what is possible later. If a brute-force recursion would solve the same subproblem many times (the same index, the same remaining amount, the same pair of prefixes), the subproblems overlap and DP applies. "Return every way" is different: listing answers is Backtracking.
The pattern
Write the recursion first, over a small state: f(i) for the best answer on the first i items, f(i, j) for two prefixes, f(a) for a remaining amount. Base cases are the states you can answer without recursing. Then memoise it (top-down) or fill a table in an order where every dependency is computed before it is read (bottom-up).
def coin_change(coins, amount):
INF = amount + 1
dp = [0] + [INF] * amount # dp[a] = fewest coins making a
for a in range(1, amount + 1):
for c in coins:
if c <= a:
dp[a] = min(dp[a], dp[a - c] + 1)
return dp[amount] if dp[amount] <= amount else -1
Cost
States × work per state for time, and the number of states for space — often cut to one or two rows, because a row reads only the one before it. Coin change above is O(amount × coins) time and O(amount) space.
Common mistakes
- A state that leaves out something the future depends on, such as whether you hold a stock or how many transactions remain.
- Filling cells in an order that reads one not yet computed.
- In counting problems, swapping the loops: coins outside counts combinations, amounts outside counts ordered sequences.
- Using 0 to mean "impossible" in a minimisation, or recursing without a memo and paying exponential time.
Start with
- Climbing Stairs: a one-dimensional recurrence.
- House Robber: a take-or-skip choice at each index.
- Coin Change: a table indexed by remaining amount.
All dynamic programming problems
Easy (11)
- Count Ways to Tile a 2 x N Floor Math
- Counting Bits Bit Manipulation
- Divisor Game Math, Brainteaser, Game Theory
- Pascal's Triangle II Array
- N-th Tribonacci Number Math, Memoization
- Fibonacci Number Math, Recursion
- Pascal's Triangle Array
- Min Cost Climbing Stairs Array
- Is Subsequence String, Two Pointers
- Best Time to Buy and Sell Stock Array
- Climbing Stairs Math, Memoization
Medium (208)
- Largest BST in a Binary Tree Tree, Depth-First Search
- Longest ZigZag Path in a Binary Tree Tree, Depth-First Search
- House Robber III Tree, Depth-First Search
- Find Good Days to Rob the Bank Array, Prefix Sum
- Minimum Increments to Equalize Leaf Paths Array, Tree, Depth-First Search
- Disconnect Path in a Binary Matrix by at Most One Flip Array, Depth-First Search, Breadth-First Search
- Floyd Warshall Graph, Shortest Path
- Count Partitions With Max-Min Difference at Most K Array, Queue, Sliding Window
- Best Time to Buy and Sell Stock V Array
- Longest Palindromic Subsequence After at Most K Operations String
- Maximum Frequency After Subarray Operation Array, Hash Table, Greedy
- Maximum Amount of Money Robot Can Earn Array, Matrix
- Count Paths With the Given XOR Value Array, Bit Manipulation, Matrix
- Count Beautiful Splits in an Array Array
- Minimum Array Sum Array
- Total Characters in String After Transformations I Hash Table, Math, String
- Maximum Points Tourist Can Earn Array, Matrix
- Find Maximum Removals From Source String Array, Hash Table, Two Pointers
- Maximum Total Damage With Spell Casting Array, Hash Table, Two Pointers
- Maximum Total Reward Using Operations I Array, Bit Manipulation
- Maximum Difference Score in a Grid Array, Matrix
- Minimum Substring Partition of Equal Character Frequency Hash Table, String, Counting
- Minimum Number of Operations to Satisfy Conditions Array, Matrix
- Number of Strings Which Can Be Rearranged to Contain Substring Math, Combinatorics
- Maximum Score After Applying Operations on a Tree Tree, Depth-First Search
- Apply Operations to Make Two Strings Equal String
- Maximum Number of Jumps to Reach the Last Index Array
- Partition String Into Minimum Beautiful Substrings Hash Table, String, Backtracking
- Decremental String Concatenation Array, String
- Minimum Path Cost in a Grid Array, Matrix
- First Day Where You Have Been in All the Rooms Array
- Egg Drop With 2 Eggs and N Floors Math
- Best Team With No Conflicts Array, Sorting
- Can I Win Math, Bit Manipulation, Memoization
- Gold Mine Problem Array, Matrix
- Maximum Sum Increasing Subsequence Array
- Longest Bitonic Subsequence Array
- Shortest Common Supersequence Length String
- Longest Repeating Subsequence String
- Optimal Strategy For A Game Array, Game Theory
- Perfect Sum Problem Array
- Subset Sum Problem Array
- Longest Common Substring String
- Rod Cutting Array
- 0/1 Knapsack Array
- Matchsticks to Square Array, Backtracking, Bitmask
- Largest 1-Bordered Square Array, Matrix
- Maximum Non Negative Product in a Matrix Array, Matrix
- Minimum Jumps to Reach Home Array, Breadth-First Search
- Find the City With the Smallest Number of Neighbors at a Threshold Distance Graph, Shortest Path
- Visit Array Positions to Maximize Score Array
- Maximum Multiplication Score Array
- Maximum Energy Boost From Two Drinks Array
- Find the Maximum Length of a Good Subsequence I Array, Hash Table
- Find All Possible Stable Binary Arrays I Prefix Sum, Combinatorics
- Maximum Number of Operations With the Same Score II Array, Memoization
- Ways to Split Array Into Good Subarrays Array, Math
- Maximize the Profit as the Salesman Array, Sorting, Binary Search
- Extra Characters in a String String, Hash Table, Trie
- Solving Questions With Brainpower Array
- Maximum Earnings From Taxi Array, Hash Table, Sorting
- Minimize the Difference Between Target and Chosen Elements Array, Matrix
- Minimum Total Space Wasted With K Resizing Operations Array
- Minimum Sideway Jumps Array, Greedy
- Closest Dessert Cost Array, Backtracking
- Guess Number Higher or Lower II Math, Game Theory
- Filling Bookcase Shelves Array
- Minimum Score Triangulation of Polygon Array
- Length of Longest Fibonacci Subsequence Array, Hash Table
- Binary Trees With Factors Array, Hash Table, Sorting
- Partition to K Equal Sum Subsets Backtracking, Bitmask
- Out of Boundary Paths Matrix
- Minimum Cost to Make All Characters Equal String, Greedy
- Minimum Number of Coins for Fruits Array, Monotonic Queue
- Minimum Increment Operations to Make Array Beautiful Array
- Two Best Non-Overlapping Events Array, Binary Search, Sorting
- Jump Game VI Array, Queue, Monotonic Queue
- Number of Smooth Descent Periods of a Stock Array, Math
- Maximum Length of Subarray With Positive Product Array, Greedy
- Fair Distribution of Cookies Backtracking, Bit Manipulation, Bitmask
- Maximum Compatibility Score Sum Backtracking, Bit Manipulation, Bitmask
- Special Permutations Array, Bit Manipulation, Bitmask
- Beautiful Arrangement Backtracking, Bit Manipulation, Bitmask
- Number of Sets of K Non-Overlapping Line Segments Math, Combinatorics
- Find the Substring With Maximum Cost Array, Hash Table, String
- Time Needed to Rearrange a Binary String String, Simulation
- Vowels of All Substrings Math, String, Combinatorics
- Optimal Division Array, Math
- Rotated Digits Math
- Longest Square Streak in an Array Array, Hash Table, Binary Search
- Find All Good Indices Array, Prefix Sum
- Check if There is a Valid Partition For The Array Array
- Maximum Alternating Subsequence Sum Array
- Maximum Absolute Sum of Any Subarray Array, Prefix Sum
- Number of Sub-arrays With Odd Sum Array, Math, Prefix Sum
- K-Concatenation Maximum Sum Array
- Maximum Subarray Sum with One Deletion Array
- Maximum Sum of Two Non-Overlapping Subarrays Array, Sliding Window, Prefix Sum
- Minimum Number of Increments on Subarrays to Form a Target Array Array, Greedy, Stack
- Partition Array for Maximum Sum Array
- Stone Game VII Array, Math, Game Theory
- Minimum Number of Work Sessions to Finish the Tasks Array, Bit Manipulation, Bitmask
- Count Fertile Pyramids in a Land Array, Matrix
- Number of Ways to Divide a Long Corridor Math, String
- Maximum Number of Non-overlapping Palindrome Substrings String, Greedy
- Count Number of Ways to Place Houses Math
- Count Number of Texts Hash Table, Math, String
- Number of Ways to Reach a Position After Exactly k Steps Math, Combinatorics
- Minimum Deletions to Make String Balanced String, Stack
- Number of Ways to Arrive at Destination Graph, Shortest Path, Topological Sort
- Largest Plus Sign Array, Matrix
- Number of Corner Rectangles Array, Matrix, Math
- Maximum Number of Moves in a Grid Array, Matrix, Breadth-First Search
- Minimum Cost Tree From Leaf Values Array, Stack, Monotonic Stack
- The Number of Beautiful Subsets Array, Hash Table, Backtracking
- Longest Binary Subsequence Less Than or Equal to K String, Greedy, Memoization
- Number of Ways to Select Buildings String, Prefix Sum
- Number of People Aware of a Secret Queue, Simulation
- Longest Ideal Subsequence Hash Table, String
- Stone Game II Array, Prefix Sum, Game Theory
- Predict the Winner Array, Recursion, Game Theory
- Count Alternating Subarrays Array, Math
- Count Ways To Build Good Strings
- Longest Arithmetic Subsequence Array, Hash Table, Binary Search
- Coin Change II Array
- Minimum Additions to Make Valid String String, Greedy, Stack
- Partition String Into Substrings With Values at Most K String, Greedy
- Video Stitching Array, Greedy, Intervals
- Max Consecutive Ones II Array, Sliding Window
- Push Dominoes String, Two Pointers, Simulation
- Longest Mountain in Array Array, Two Pointers
- Bitwise ORs of Subarrays Bit Manipulation, Array
- Flip String to Monotone Increasing String, Bit Manipulation
- Super Ugly Number Math, Heap
- Integer Replacement Bit Manipulation, Greedy
- Minimum Operations to Reduce an Integer to 0 Bit Manipulation, Greedy
- Count Substrings That Differ by One Character String
- Count Number of Teams Array
- Uncrossed Lines Array
- Minimum ASCII Delete Sum for Two Strings String
- Longest Palindromic Subsequence String
- Unique Binary Search Trees Math
- Domino and Tromino Tiling
- Paint House Array
- Paint Fence
- As Far from Land as Possible Array, Breadth-First Search, Matrix
- Rotate Function Array, Math
- Sort Integers by The Power Value Memoization, Sorting
- Sum of Subarray Minimums Array, Stack, Monotonic Stack
- Minimum Time to Make Rope Colorful Array, String, Greedy
- Knight Dialer
- 2 Keys Keyboard Math
- Maximum Length of Pair Chain Array, Greedy, Sorting
- Longest Turbulent Subarray Array, Sliding Window
- Number of Dice Rolls With Target Sum
- Best Sightseeing Pair Array
- Maximum Sum Circular Subarray Array, Divide and Conquer, Queue
- Minimum Cost For Tickets Array
- Longest String Chain Array, Hash Table, Two Pointers
- Combination Sum IV Array
- Ones and Zeroes Array, String
- Last Stone Weight II Array
- Stone Game Array, Math, Game Theory
- Count Numbers with Unique Digits Math, Backtracking
- Ugly Number II Hash Table, Math, Heap
- Integer Break Math
- Perfect Squares Math, Breadth-First Search
- Triangle Array
- Minimum Falling Path Sum Array, Matrix
- Interleaving String String
- Delete Operation for Two Strings String
- Count Sorted Vowel Strings Math, Combinatorics
- Arithmetic Slices Array
- Wiggle Subsequence Array, Greedy
- Number of Longest Increasing Subsequence Array, Binary Indexed Tree
- Longest Arithmetic Subsequence of Given Difference Array, Hash Table
- Maximum Length of Repeated Subarray Array, Binary Search, Sliding Window
- Best Time to Buy and Sell Stock with Transaction Fee Array, Greedy
- Best Time to Buy and Sell Stock with Cooldown Array
- Delete and Earn Array, Hash Table
- Count Square Submatrices with All Ones Array, Matrix
- Maximal Square Array, Matrix
- Unique Paths II Array, Matrix
- Minimum Path Sum Array, Matrix
- Longest Subarray of 1's After Deleting One Element Array, Sliding Window
- Valid Parenthesis String String, Stack, Greedy
- Generate Parentheses String, Backtracking
- Cheapest Flights Within K Stops Graph, Shortest Path
- 01 Matrix Array, Matrix, Breadth-First Search
- Target Sum Array, Backtracking
- Edit Distance String
- Longest Common Subsequence String
- Partition Equal Subset Sum Array
- Unique Paths Math, Combinatorics
- Decode Ways String
- Word Break String, Hash Table, Trie
- Longest Increasing Subsequence Array, Binary Search
- Coin Change II Array
- Coin Change Array, Breadth-First Search
- House Robber II Array
- House Robber Array
- Best Time to Buy and Sell Stock II Array, Greedy
- Jump Game II Array, Greedy
- Jump Game Array, Greedy
- Palindromic Substrings String
- Longest Palindromic Substring String
- Maximum Product Subarray Array
- Maximum Subarray Array, Divide and Conquer
Hard (183)
- Maximum Sum BST in Binary Tree Tree, Depth-First Search, Recursion
- Binary Tree Cameras Tree, Depth-First Search, Greedy
- Binary Tree Maximum Path Sum Tree, Depth-First Search, Recursion
- Maximum Product of the Length of Two Palindromic Substrings String, Rolling Hash, Hash Table
- Longest Chunked Palindrome Decomposition Two Pointers, String, Greedy
- Time Taken to Mark All Nodes Tree, Depth-First Search, Graph
- Count Visited Nodes in a Directed Graph Graph, Memoization
- Count Valid Paths in a Tree Math, Tree, Depth-First Search
- Minimum Edge Reversals So Every Node Is Reachable Depth-First Search, Breadth-First Search, Graph
- Minimize the Total Price of the Trips Array, Tree, Depth-First Search
- Minimum Number of Visited Cells in a Grid Array, Stack, Breadth-First Search
- Cat and Mouse Graph, Topological Sort, Memoization
- Length of Longest V-Shaped Diagonal Segment Array, Memoization, Matrix
- Sum of Good Subsequences Array, Hash Table
- Find the Number of Subsequences With Equal GCD Array, Math, Number Theory
- Find the Original Typed String II String, Prefix Sum
- Count The Number of Winning Sequences String
- Find the Maximum Sequence Value of Array Array, Bit Manipulation
- Maximum XOR Score Subarray Queries Array
- Select Cells in Grid With Maximum Score Array, Bit Manipulation, Matrix
- Find the Count of Monotonic Pairs I Array, Math, Combinatorics
- Find the Maximum Length of a Good Subsequence II Array, Hash Table
- Minimum Sum of Values by Dividing Array Array, Binary Search, Bit Manipulation
- Find the Sum of Subsequence Powers Array, Sorting
- Find the Sum of the Power of All Subsequences Array
- Maximize Consecutive Elements in an Array After Modification Array, Sorting
- Maximize the Number of Partitions After Operations String, Bit Manipulation, Bitmask
- Count the Number of Powerful Integers Math, String, Digit DP
- Find Maximum Non-decreasing Array Length Array, Binary Search, Stack
- Maximum Points After Collecting Coins From All Nodes Array, Bit Manipulation, Tree
- Minimum Changes to Make K Semi-palindromes Two Pointers, String
- Count of Sub-Multisets With Bounded Sum Array, Hash Table, Sliding Window
- Number of Beautiful Integers in the Range Math, Digit DP
- Count of Integers Math, String, Digit DP
- Maximum Strictly Increasing Cells in a Matrix Array, Hash Table, Binary Search
- Count Increasing Quadruplets Array, Binary Indexed Tree, Enumeration
- Minimum Total Distance Traveled Array, Sorting
- Maximum Deletions on a String String, Rolling Hash, String Matching
- Substring With Largest Variance Array
- Check if There Is a Valid Parentheses String Path Array, Matrix
- The Earliest and Latest Rounds Where Players Compete Memoization
- Maximum Number of Groups Getting Fresh Donuts Array, Bit Manipulation, Memoization
- Make the XOR of All Segments Equal to Zero Array, Bit Manipulation
- Delivering Boxes from Storage to Ports Array, Segment Tree, Queue
- Minimum Number of Removals to Make Mountain Array Array, Binary Search, Greedy
- Minimum Cost to Connect Two Groups of Points Array, Bit Manipulation, Matrix
- K Inverse Pairs Array Prefix Sum
- Non-negative Integers without Consecutive Ones Digit DP, Bit Manipulation
- Freedom Trail String, Depth-First Search, Breadth-First Search
- Word Wrap Array
- Boolean Parenthesization String
- Matrix Chain Multiplication Array
- Zuma Game String, Breadth-First Search, Memoization
- Remove Boxes Array, Memoization
- Stickers to Spell Word String, Backtracking, Bitmask
- Distribute Repeating Integers Array, Backtracking, Bitmask
- Number of Paths with Max Score Array, Matrix
- Sum of Distances in Tree Tree, Depth-First Search, Graph
- Parallel Courses III Array, Graph, Topological Sort
- Largest Color Value in a Directed Graph Graph, Topological Sort, Memoization
- Palindrome Partitioning III String
- Number of Beautiful Partitions String, Prefix Sum
- Selling Pieces of Wood Array, Memoization
- Minimum Time to Remove All Cars Containing Illegal Goods String, Prefix Sum
- Minimum Operations to Make the Array K-Increasing Array, Binary Search
- Number of Unique Good Subsequences String
- Count Number of Special Subsequences Array
- Minimum Skips to Arrive at Meeting On Time Array
- Maximize Palindrome Length From Subsequences String
- Number of Ways to Form a Target String Given a Dictionary Array, String
- Count All Possible Routes Array, Memoization
- Minimum Number of Days to Eat N Oranges Memoization
- Paint House III Array
- Number of Ways of Cutting a Pizza Array, Matrix, Prefix Sum
- Pizza With 3n Slices Array, Greedy, Heap (Priority Queue)
- Jump Game V Array, Sorting
- Minimum Distance to Type a Word Using Two Fingers String
- Maximum Profit in Job Scheduling Array, Binary Search, Sorting
- Dice Roll Simulation Array
- Stone Game V Array, Math, Game Theory
- Minimum Cost to Merge Stones Array, Prefix Sum
- Super Egg Drop Math, Binary Search
- Maximum Sum of 3 Non-Overlapping Subarrays Array, Prefix Sum, Sliding Window
- Arithmetic Slices II - Subsequence Array, Hash Table
- Decode Ways II String
- Minimum Swaps To Make Sequences Increasing Array
- Maximum Score from Performing Multiplication Operations Array
- Maximum Score Of Spliced Array Array
- Delete Columns to Make Sorted III Array, String
- Minimum Time to Finish the Race Array
- Kth Smallest Instructions Array, Math, Combinatorics
- Minimum Difference in Sums After Removal of Elements Array, Heap (Priority Queue)
- Longest Increasing Subsequence II Array, Segment Tree, Divide and Conquer
- Maximize Score After N Operations Math, Number Theory, Bitmask
- Parallel Courses II Bit Manipulation, Graph, Bitmask
- Number of Ways to Wear Different Hats to Each Other Array, Bit Manipulation, Bitmask
- Maximum Students Taking Exam Bit Manipulation, Matrix, Bitmask
- Minimum XOR Sum of Two Arrays Array, Bit Manipulation, Bitmask
- Numbers With Repeated Digits Math, Digit DP, Combinatorics
- Numbers At Most N Given Digit Set Math, Digit DP
- Poor Pigs Math, Combinatorics
- Palindrome Partitioning IV String
- Word Break II Hash Table, String, Backtracking
- Concatenated Words String, Depth-First Search, Trie
- Find the String with LCP String, Greedy, Matrix
- Count Palindromic Subsequences String, Counting
- Total Appeal of A String String, Hash Table
- Student Attendance Record II Combinatorics
- Count Ways to Make Array With Product Array, Math, Combinatorics
- Count the Number of Ideal Arrays Math, Combinatorics, Number Theory
- Number of Ways to Rearrange Sticks With K Sticks Visible Math, Combinatorics
- The Number of Good Subsets Array, Math, Bit Manipulation
- Number of Ways to Reorder Array to Get Same BST Array, Math, Divide and Conquer
- Make Array Strictly Increasing Array, Binary Search, Sorting
- Odd Even Jump Array, Stack, Monotonic Stack
- Maximum Number of Events That Can Be Attended II Array, Binary Search, Sorting
- Painting the Walls Array
- Number of Ways to Separate Numbers String, Suffix Array, Prefix Sum
- Painting a Grid With Three Different Colors Bitmask
- Minimum Incompatibility Array, Bit Manipulation, Bitmask
- Number of Distinct Roll Sequences Memoization
- Form Largest Integer With Digits That Add up to Target Array, String
- Build Array Where You Can Find The Maximum Exactly K Comparisons Prefix Sum
- Stone Game VIII Array, Math, Prefix Sum
- Allocate Mailboxes Array, Math, Sorting
- Constrained Subsequence Sum Array, Queue, Sliding Window
- Restore the Array String
- Count All Valid Pickup and Delivery Options Math, Combinatorics
- Maximum Height by Stacking Cuboids Array, Sorting
- Cherry Pickup II Array, Matrix
- Strange Printer String
- Number of Ways to Stay in the Same Place After Some Steps
- Maximum Value of K Coins From Piles Array, Prefix Sum
- Count Special Integers Math, Combinatorics
- Number of Great Partitions Array
- Minimum Cost to Split an Array Array, Hash Table, Counting
- Paths in Matrix Whose Sum Is Divisible by K Array, Matrix
- Count Different Palindromic Subsequences String
- Valid Palindrome III String
- String Compression II String
- Number of Increasing Paths in a Grid Array, Matrix, Depth-First Search
- Number of Restricted Paths From First to Last Node Graph, Shortest Path, Heap (Priority Queue)
- Minimum Moves to Spread Stones Over Grid Array, Matrix, Breadth-First Search
- Longest Increasing Path in a Matrix Array, Matrix, Depth-First Search
- Maximal Rectangle Array, Matrix, Stack
- Minimum Difficulty of a Job Schedule Array
- Minimum Cost to Cut a Stick Array, Sorting
- Minimum White Tiles After Covering With Carpets String, Prefix Sum
- Number of Ways to Earn Points Array
- Scramble String String
- Number of Music Playlists Math, Combinatorics
- Profitable Schemes Array
- Distinct Subsequences II String
- Cherry Pickup Array, Matrix
- Number of Ways to Paint N × 3 Grid
- Tallest Billboard Array
- Best Time to Buy and Sell Stock IV Array
- Burst Balloons Array
- Frog Jump Array, Hash Table
- Minimum Falling Path Sum II Array, Matrix
- Dungeon Game Array, Matrix
- Minimum Number of Refueling Stops Array, Greedy, Heap
- Minimum Number of Taps to Open to Water a Garden Array, Greedy, Intervals
- Russian Doll Envelopes Array, Binary Search, Sorting
- Split Array Largest Sum Array, Binary Search, Greedy
- Minimum Number of Flips to Make the Binary String Alternating String, Sliding Window, Greedy
- Minimum Window Subsequence String, Two Pointers, Sliding Window
- Count the Number of Square-Free Subsets Bit Manipulation, Bitmask, Math
- Maximum AND Sum of Array Bit Manipulation, Bitmask
- Minimum One Bit Operations to Make Integers Zero Bit Manipulation, Math
- Largest Multiple of Three Array, Greedy, Math
- Stone Game IV Math, Game Theory
- Stone Game III Array, Game Theory
- Palindrome Partitioning II String
- Wildcard Matching String, Greedy
- Distinct Subsequences String
- Max Dot Product Between Two Subsequences Array
- Minimum Insertion Steps to Make a String Palindrome String
- Longest Valid Parentheses String, Stack
- Count Vowels Permutation
- Best Time to Buy and Sell Stock III Array
- Regular Expression Matching String, Recursion
- Trapping Rain Water Array, Two Pointers, Stack
Companies that ask dynamic programming problems
- Amazon 343 problems on dynamic programming
- Google 324 problems on dynamic programming
- Microsoft 82 problems on dynamic programming
- Meta 41 problems on dynamic programming
- Adobe 31 problems on dynamic programming
- Uber 24 problems on dynamic programming
- Flipkart 13 problems on dynamic programming
- Bloomberg 12 problems on dynamic programming
- Morgan Stanley 10 problems on dynamic programming
- Sprinklr 10 problems on dynamic programming
- Airbnb 7 problems on dynamic programming
- Intuit 7 problems on dynamic programming
Next topic: Memoization