200+ Problems on Dynamic Programming
Welcome to my Dynamic Programming (DP) Problem Sheet! This is an ever-growing list of DP problems from LeetCode. Dynamic programming is a powerful technique used to solve optimization problems by breaking them down into simpler subproblems and storing their solutions to avoid redundant computations.
About
This collection includes problems categorized into different types of dynamic programming approaches such as linear DP, knapsack, multi-dimensional DP, interval DP, bit DP, digit DP, DP on trees, string DP, probability DP, classic DPs, DP with advanced techniques, and more.
Accessing Solutions
You can find solutions to these problems in the GitHub repository CAlgo/DPSheet.
Disclaimer
Please note that dynamic programming can be a challenging topic, and understanding these problems may require some background knowledge in algorithms and data structures. However, don’t get discouraged! Practice makes perfect, and each solved problem brings you one step closer to becoming proficient in dynamic programming.
Linear DP
- Climbing Stairs
- Best Time to Buy and Sell Stock
- Min Cost Climbing Stairs
- Divisor Game
- Decode Ways
- Unique Binary Search Trees
- House Robber
- Perfect Squares
- Best Time to Buy and Sell Stock with Cooldown
- Coin Change
- Counting Bits
- Integer Break
- Count Numbers with Unique Digits
- Wiggle Subsequence
- Partition Equal Subset Sum
- Maximum Length of Pair Chain
- Best Time to Buy and Sell Stock with Transaction Fee
- Delete and Earn
- Domino and Tromino Tiling
- Knight Dialer
- Minimum Cost for Tickets
- Partition Array for Maximum Sum
- Filling Bookcase Shelves
- Longest Arithmetic Subsequence of Given Difference
- Greatest Sum Divisible by Three
- Best Time to Buy and Sell Stock III
- Student Attendance Record II
- Decode Ways II
- Triples with Bitwise AND Equal To Zero
- Maximum Profit in Job Scheduling
- Minimum Number of Taps to Open to Water a Garden
- Count All Valid Pickup and Delivery Options
- Stone Game III
- Restore the Array
- Form Largest Integer with Digits That Add up to Target
- Stone Game IV
- Coin Change 2
Knapsack
- House Robber II
- Ones and Zeroes
- Target Sum
- Shopping Offers
- 2 Keys Keyboard
- Minimum Swaps to Make Sequences Increasing
- Best Team With No Conflicts
- Profitable Schemes
- Tallest Billboard
- Pizza With 3n Slices
- Reducing Dishes
Multi Dimensions DP
- Triangle
- Combination Sum IV
- Out of Boundary Paths
- Knight Probability in Chessboard
- Champagne Tower
- Largest Sum of Averages
- Minimum Falling Path Sum
- Video Stitching
- Longest Arithmetic Subsequence
- Stone Game II
- Number of Dice Rolls With Target Sum
- Dice Roll Simulation
- Number of Sets of K Non-Overlapping Line Segments
- Best Time to Buy and Sell Stock IV
- Create Maximum Number
- Frog Jump
- Split Array Largest Sum
- Freedom Trail
- Minimum Number of Refueling Stops
- Number of Music Playlists
- Count Vowels Permutation
- Minimum Falling Path Sum II
- Minimum Distance to Type a Word Using Two Fingers
- Minimum Difficulty of a Job Schedule
- Number of Ways to Paint N × 3 Grid
- Build Array Where You Can Find The Maximum Exactly K Comparisons
- Number of Ways of Cutting a Pizza
- Paint House III
- Count All Possible Routes
- Cherry Pickup II
Bit DP
- Can I Win
- Partition to K Equal Sum Subsets
- Stickers to Spell Word
- Shortest Path Visiting All Nodes
- Smallest Sufficient Team
- Maximum Students Taking Exam
- Number of Ways to Wear Different Hats to Each Other
- Minimum Cost to Connect Two Groups of Points
- Maximum Number of Achievable Transfer Requests
- Distribute Repeating Integers
- Maximize Grid Happiness
- Find Minimum Time to Finish All Jobs
Digit DP
- Non-negative Integers without Consecutive Ones
- Numbers At Most N Given Digit Set
- Numbers With Repeated Digits
DP on Trees
- Unique Binary Search Trees II
- House Robber III
- Maximum Product of Splitted Binary Tree
- Linked List in Binary Tree
- Longest ZigZag Path in a Binary Tree
- Binary Tree Cameras
- Maximum Sum BST in Binary Tree
- Number of Ways to Reorder Array to Get Same BST
- Find the Maximum Sum of Node Values
String DP
- Is Subsequence
- Palindrome Partitioning
- Palindrome Partitioning II
- Word Break
- Unique Substrings in Wraparound String
- Minimum ASCII Delete Sum for Two Strings
- Longest String Chain
- Longest Happy String
- Longest Valid Parentheses
- Distinct Subsequences
- Word Break II
- Count the Repetitions
- Concatenated Words
- Count Different Palindromic Subsequences
- Distinct Subsequences II
- Longest Chunked Palindrome Decomposition
- Palindrome Partitioning III
- Find All Good Strings
- String Compression II
- Number of Ways to Form a Target String Given a Dictionary
Probability DP
Classic DPs
A. Cadane’s Algorithm
- Maximum Subarray
- Maximum Product Subarray
- Bitwise ORs of Subarrays
- Longest Turbulent Subarray
- Maximum Subarray Sum with One Deletion
- K Concatenation Maximum Sum
- Largest Divisible Subset
- Length of Longest Fibonacci Subsequence
B. LCS
- Longest Palindromic Substring
- Longest Palindromic Subsequence
- Maximum Length of Repeated Subarray
- Longest Common Subsequence
- Regular Expression Matching
- Wildcard Matching
- Edit Distance
- Interleaving String
- Shortest Common Supersequence
- Minimum Insertion Steps to Make a String Palindrome
- Max Dot Product of Two Subsequences
C. LIS
- Longest Increasing Subsequence
- Number of Longest Increasing Subsequence
- Russian Doll Envelopes
- Delete Columns to Make Sorted III
- Minimum Number of Removals to Make Mountain Array
- Maximum Height by Stacking Cuboids
- Make Array Strictly Increasing
D. 2D Grid Traversal
- Unique Paths
- Unique Paths II
- Minimum Path Sum
- Maximum Non-Negative Product in a Matrix
- Where Will the Ball Fall
- Dungeon Game
- Cherry Pickup
- Number of Paths with Max Score
- Kth Smallest Instructions
E. Cumulative Sum
- Range Sum Query - Immutable
- Maximal Square
- Range Sum Query 2D - Immutable
- Largest Plus Sign
- Push Dominoes
- Largest 1-Bordered Square
- Count Square Submatrices with All Ones
- Matrix Block Sum
- Maximum Points You Can Obtain from Cards
- Count Submatrices with All Ones
- Ways to Make a Fair Array
- Maximal Rectangle
- Max Sum of Rectangle No Larger Than K
- Super Washing Machines
- Maximum Sum of 3 Non-Overlapping Subarrays
- Number of Submatrices That Sum to Target
- Get the Maximum Score
F. Hashmap (SubArray)
- Continuous Subarray Sum
- Find Two Non-overlapping Sub-arrays Each With Target Sum
- Maximum Number of Non-overlapping Subarrays With Sum Equals Target
DP + Alpha (Tricks/DS)
- Arithmetic Slices II - Subsequence
- Odd Even Jump
- Constrained Subsequence Sum
- Delivering Boxes from Storage to Ports
Insertion DP
Graph DP
- Cheapest Flights Within K Stops
- Find the Shortest Superstring
- Count Visited Nodes in a Directed Graph
- Longest Increasing Path in a Matrix
- Number of Restricted Paths From First to Last Node
Memoization
- Minimum Jumps to Reach Home
- Scramble String
- Tiling a Rectangle with the Fewest Squares
- Number of Ways to Stay in the Same Place After Some Steps
- Jump Game V
- Minimum Number of Days to Eat N Oranges
Binary Lifting
Math
- Ugly Number II
- Count Sorted Vowel Strings
- Race Car
- Super Egg Drop
- Least Operators to Express Number
- Largest Multiple of Three
- Minimum One Bit Operations to Make Integers Zero
Happy Programming!
This post is licensed under CC BY 4.0 by the author.