Skip to content
DSA
Go
dp from start
DP
graph from start
Graphs
Miscellaneous
system
System design HLD
System design LLD
Kubernetes & Docker
SQL
LLD leetcode
Goldman Sachs
Share
Explore

dp from start


Table 12
Fibonacci, Climbing Stairs
Either (memoization is simpler)
Both are O(n) time and space.
Knapsack, LCS, Edit Distance
Requires filling an entire table; tabulation is cleaner and faster.
Tree/Graph DP
Recursive structure aligns with tree/graph traversal.
Digit DP
Recursive digit-by-digit processing is intuitive.
Grid Path Problems
Iterative row/column filling is natural.
Subset Sum, Partition Problems
All subproblems are needed; tabulation avoids recursion overhead.
There are no rows in this table
⁠

Here’s a topic-wise list of non-premium LeetCode DP problems, categorized by pattern. These problems are curated to help you build intuition step by step, from beginner to advanced.
⁠

1. 1D Dynamic Programming

Pattern: Solve problems using a 1D array where dp[i] depends on previous values.
Table 13
Problem
Linksr
Difficulty
Checkbox
Climbing Stairs
Fibonacci Number
Min Cost Climbing Stairs
House Robber
House Robber II
Delete and Earn
Best Time to Buy and Sell Stock
Best Time to Buy and Sell Stock II
Best Time to Buy and Sell Stock with Cooldown
Coin Change
Word Break
Decode Ways
Jump Game
Jump Game II
Maximum Subarray
There are no rows in this table
⁠
⁠

2. 2D Dynamic Programming (Grid/Table)

Pattern: Use a 2D table where dp[i][j] depends on previous rows/columns.
Table 14
problem
link
difficulty
Checkbox
Edit Distance
Longest Common Subsequence (LCS)
Distinct Subsequences
Interleaving String
Longest Palindromic Subsequence
Minimum Path Sum
Unique Paths
Unique Paths II
Longest Increasing Path in a Matrix
Maximum Length of Repeated Subarray
There are no rows in this table
⁠

⁠

3. Knapsack Problems

Pattern: Select items to maximize value without exceeding a weight/capacity constraint.
Table 15
Problem
LeetCode Link
Difficulty
Checkbox
0/1 Knapsack (Classic)
[Not directly on LeetCode, but see "Partition Equal Subset Sum" below]
Partition Equal Subset Sum
Target Sum
Ones and Zeroes
Last Stone Weight II
Coin Change II
There are no rows in this table
⁠

⁠

4. Interval DP

Pattern: Break problems into intervals and combine results.
Table 16
Problem
LeetCode Link
Difficulty
Checkbox
Burst Balloons
Matrix Chain Multiplication
[Not directly on LeetCode, but see "Minimum Score Triangulation of Convex Polygon" below]
Minimum Score Triangulation of Convex Polygon
Palindromic Substrings
There are no rows in this table
⁠

⁠

5. State Compression DP

Pattern: Use bitmasking or states to represent subsets or configurations.
Table 17
Problem
LeetCode Link
Difficulty
Checkbox
Subsets
Subset Sum
[Not directly on LeetCode, but see "Partition Equal Subset Sum" above]
Can I Win
Counting Bits
There are no rows in this table
⁠


⁠

6. Digit DP

Pattern: Process numbers digit by digit with constraints.
Table 18
Problem
LeetCode Link
Difficulty
Checkbox
Numbers With Same Consecutive Differences
Count Numbers with Unique Digits
357. Count Numbers with Unique Digits
Digit DP Template (Not a specific problem, but useful for problems like "Numbers At Most N Given Digit Set")
There are no rows in this table
⁠


⁠

7. Game Theory DP

Pattern: Model games where players take turns (e.g., minimax).
Table 19
Problem
LeetCode Link
Difficulty
Checkbox
Predict the Winner
486. Predict the Winner
Stone Game
877. Stone Game
Nim Game
292. Nim Game
There are no rows in this table
⁠

⁠

8. String DP

Pattern: DP problems involving string manipulation or matching.
Table 20
Problem
LeetCode Link
Difficulty
Checkbox
Longest Increasing Subsequence (LIS)
Medium
Longest Common Substring
[Not directly on LeetCode, but see "Minimum Window Substring" or "LCS" above]
Medium
Wildcard Matching
Hard
Regular Expression Matching
Hard
There are no rows in this table
⁠

⁠

9. Miscellaneous DP Problems

Pattern: Unique DP problems that don’t fit neatly into the above categories.
Table 21
Longest Valid Parentheses
32. Longest Valid Parentheses
Hard
Perfect Squares
Integer Break
Out of Boundary Paths
Knight Probability in Chessboard
Cherry Pickup
Dungeon Game
There are no rows in this table
⁠

⁠

10. DP on Trees

Pattern: DP problems involving tree structures.
Table 22
Problem
LeetCode Link
Difficulty
House Robber III
Medium
Binary Tree Maximum Path Sum
Hard
There are no rows in this table
⁠

⁠

How to Use This List

Start with 1D DP: Master the basics with problems like Fibonacci, Climbing Stairs, and Coin Change.
Move to 2D DP: Tackle grid-based problems like LCS, Edit Distance, and Unique Paths.
Knapsack Problems: Practice selecting items under constraints.
Interval DP: Learn to break problems into intervals and combine results.
State Compression and Digit DP: Explore bitmasking and digit-by-digit processing.
Game Theory and String DP: Apply DP to games and string manipulation.
Miscellaneous and Tree DP: Challenge yourself with unique and advanced problems.
⁠

Tips for Practicing

Solve in order: Start with easier problems and gradually move to harder ones.
Time yourself: Aim to solve each problem within 30-45 minutes.
Review solutions: After solving, compare your approach with the optimal solution.
Revisit problems: Solve the same problem again after a few days to reinforce learning.
Draw the DP table: Visualizing small cases helps you understand the pattern.


Want to print your doc?
This is not the way.
Try clicking the ··· in the right corner or using a keyboard shortcut (
CtrlP
) instead.