Skip to main content

Master Dynamic Programming - Complete Pattern Guide

· 10 min read

Hey everyone! Many of us struggle with Dynamic Programming and often skip it during interview preparation. This might be because DP seems vast and overwhelming, and people tend to memorize solutions instead of understanding patterns. However, if you break down DP into clear patterns and master each one, it becomes much more manageable. So I've compiled a comprehensive list of patterns you should know for your interview preparation!

DP vs Greedy: When to Use Which?​

Before diving into patterns, let's understand the fundamental difference between DP and Greedy:

Problem: You're a robber with two streets to rob. Each house has some money. You can rob houses from both streets, but you cannot rob two adjacent houses from the same street (alarms will trigger). What's the maximum money you can steal?

Street A: [2, 7, 9, 3, 1]
Street B: [3, 2, 6, 8, 2]

Greedy Robber: "I'll always rob the house with most money available!"

  • Rob B[0] = 3 (greedy)
  • Rob A[1] = 7
  • Rob B[2] = 6
  • Rob A[3] = 3
  • Rob B[4] = 2
  • Total: 21

DP Robber: "Let me consider all valid combinations!"

  • Option 1: A[0]=2, B[1]=2, A[2]=9, B[3]=8, A[4]=1 → Total = 22
  • Option 2: B[0]=3, A[1]=7, B[2]=6, A[3]=3, B[4]=2 → Total = 21
  • Best: 22

Why Greedy Failed: By greedily picking B[0] first, it blocked access to the optimal combination that includes both 9 and 8 from different streets!

When Greedy Works: Problems with the "greedy choice property" where local optimal leads to global optimal (e.g., Activity Selection, Huffman Coding) When DP is Needed: Problems requiring exploring multiple choices where greedy fails (e.g., most optimization problems, counting problems)

Pattern 1: Linear DP (1D)​

Why This Pattern Matters: This is the foundation of DP. If you can't solve Linear DP, you'll struggle with everything else. These problems teach you the core concept of breaking problems into subproblems and building solutions incrementally.

Practice Problems:

  1. Climbing Stairs
  2. House Robber
  3. Min Cost Climbing Stairs
  4. Word Break
  5. Decode Ways
  6. House Robber II

Pattern 2: Longest Increasing Subsequence (LIS)​

Why This Pattern Matters: LIS is one of the most important DP patterns with applications in version control systems, patience sorting, box stacking problems, and more. The O(n log n) solution using binary search is a must-know optimization technique.

Practice Problems:

  1. Longest Increasing Subsequence
  2. Number of Longest Increasing Subsequence
  3. Russian Doll Envelopes
  4. Maximum Length of Pair Chain
  5. Find the Longest Valid Obstacle Course at Each Position

Pattern 3: Knapsack (0/1, Unbounded, Bounded)​

Why This Pattern Matters: One of the most versatile DP patterns. Appears in resource allocation, optimization problems, and many interview questions. Understanding the difference between 0/1 and unbounded variants is crucial.

0/1 Knapsack (Each item used once):

  1. Partition Equal Subset Sum
  2. Target Sum
  3. Last Stone Weight II
  4. Ones and Zeroes
  5. Partition Array Into Two Arrays to Minimize Sum Difference

Unbounded Knapsack (Items can be used multiple times):

  1. Coin Change
  2. Coin Change 2
  3. Combination Sum IV
  4. Perfect Squares
  5. Minimum Cost For Tickets

Pattern 4: Grid DP​

Why This Pattern Matters: Extremely common in interviews, especially at FAANG. Tests your ability to think in 2D state space and handle multiple transition directions.

Practice Problems:

  1. Unique Paths
  2. Unique Paths II
  3. Minimum Path Sum
  4. Maximal Square
  5. Maximal Rectangle
  6. Minimum Falling Path Sum
  7. Count Square Submatrices with All Ones
  8. Triangle

Pattern 5: String DP​

Why This Pattern Matters: Text processing and string manipulation problems are ubiquitous. This pattern appears in bioinformatics, text editors, version control systems, and natural language processing.

Practice Problems:

  1. Longest Common Subsequence
  2. Edit Distance
  3. Delete Operation for Two Strings
  4. Minimum ASCII Delete Sum for Two Strings
  5. Shortest Common Supersequence
  6. Longest Palindromic Subsequence
  7. Longest Palindromic Substring
  8. Palindromic Substrings
  9. Regular Expression Matching
  10. Wildcard Matching

Pattern 6: Interval DP​

Why This Pattern Matters: Tests ability to think about problems in ranges/intervals. Common in scheduling, matrix chain multiplication type problems, and game theory.

Practice Problems:

  1. Burst Balloons
  2. Minimum Score Triangulation of Polygon
  3. Minimum Cost Tree From Leaf Values
  4. Unique Binary Search Trees
  5. Unique Binary Search Trees II
  6. Minimum Cost to Merge Stones
  7. Guess Number Higher or Lower II

Pattern 7: State Machine DP​

Why This Pattern Matters: Models problems where you transition between different states with specific rules. Critical for stock trading problems and any scenario with state transitions.

Practice Problems:

  1. Best Time to Buy and Sell Stock
  2. Best Time to Buy and Sell Stock II
  3. Best Time to Buy and Sell Stock III
  4. Best Time to Buy and Sell Stock IV
  5. Best Time to Buy and Sell Stock with Cooldown
  6. Best Time to Buy and Sell Stock with Transaction Fee

Pattern 8: Tree DP​

Why This Pattern Matters: Combines tree traversal with DP. Important for system design (like designing file systems) and optimization problems on hierarchical structures.

Practice Problems:

  1. House Robber III
  2. Binary Tree Maximum Path Sum
  3. Diameter of Binary Tree
  4. Binary Tree Cameras
  5. Maximum Sum BST in Binary Tree
  6. Difference Between Maximum and Minimum Price Sum

Pattern 9: Digit DP​

Why This Pattern Matters: Specialized pattern for counting numbers with certain properties. Appears in competitive programming and some advanced interviews.

Practice Problems:

  1. Number of Digit One
  2. Count Numbers with Unique Digits
  3. Numbers At Most N Given Digit Set
  4. Numbers With Repeated Digits
  5. Count Special Integers

Pattern 10: Game Theory DP (Minimax)​

Why This Pattern Matters: Models two-player games where both play optimally. Important for AI, game development, and adversarial scenarios.

Practice Problems:

  1. Predict the Winner
  2. Stone Game
  3. Stone Game II
  4. Stone Game III
  5. Can I Win
  6. Stone Game IV

Pattern 11: Bitmask DP​

Why This Pattern Matters: Powerful technique for problems with small sets (≤20 elements) where you need to track subsets. Essential for Traveling Salesman Problem variants and NP-hard problem approximations.

Practice Problems:

  1. Partition to K Equal Sum Subsets
  2. Shortest Path Visiting All Nodes
  3. Find the Shortest Superstring
  4. Smallest Sufficient Team
  5. Number of Ways to Wear Different Hats to Each Other
  6. Minimum Number of Work Sessions to Finish the Tasks

Pattern 12: DP on Subsequences​

Why This Pattern Matters: Critical for array partitioning and subset generation problems. Teaches how to handle exponential search spaces efficiently.

Practice Problems:

  1. Distinct Subsequences
  2. Distinct Subsequences II
  3. Arithmetic Slices II - Subsequence
  4. Number of Unique Good Subsequences
  5. Constrained Subsequence Sum

Pattern 13: Probability DP​

Why This Pattern Matters: Models uncertain outcomes. Important for risk analysis, game development, and any scenario involving randomness or probability.

Practice Problems:

  1. Knight Probability in Chessboard
  2. Soup Servings
  3. New 21 Game
  4. Toss Strange Coins
  5. Probability of a Two Boxes Having The Same Number of Distinct Balls

Best Resources to Master DP​

  1. AtCoder DP Contest- 26 curated problems with perfect difficulty progression
  2. Striver's DP Series- 50+ videos covering memoization, tabulation, and space optimization.
  3. Aditya Verma's DP Playlist- Exceptional for Knapsack variants with shorter, focused videos (15-20 min).
  4. CSES Problem Set- Intermediate to advanced practice. These problems test core concepts and build solving speed.

Final Thoughts​

DP is about recognizing patterns, not memorizing solutions. Once you see the pattern, the solution becomes mechanical. Spend time understanding why each pattern works, not just how to code it.

Feel free to add some best problems in the comments

Good luck, and happy coding! 🚀

If this guide helped you, please upvote and share with others!