Skip to main content

Part 5: The Essential 10 - Mastering DP for Big Tech

The canonical foundation for Dynamic Programming interview preparation

Introduction​

These ten LeetCode problems represent the canonical foundation for mastering Dynamic Programming patterns asked at Google, Meta, Amazon, Microsoft, and Apple. Each problem teaches a fundamental pattern that transfers to 10-20+ similar problems, making them force multipliers for interview preparation.

All appear in curated lists like Blind 75, NeetCode 150, or are explicitly recommended in top DP curricula. The selection prioritizes pattern clarity, interview frequency, and transferability over difficulty alone.

1. Linear DP (1D Array): House Robber​

LeetCode 198 | Medium

Why this problem is essential​

House Robber is the quintessential Linear DP problem that perfectly teaches 1D state transitions with constraints. While Climbing Stairs is more basic, House Robber demonstrates the pattern at the ideal difficulty level and appears in virtually every curated interview list. It's the gold standard for learning "take it or leave it" decision-making in DP.

Key insight taught​

The fundamental state transition dp[i] = max(dp[i-1], dp[i-2] + nums[i]) teaches decision-making at each index based on previous states with constraints (cannot take adjacent elements).

Space optimization from O(n) to O(1) by tracking only the last two states (rob1, rob2) demonstrates dimension reduction thinking.

Pattern transferability​

This pattern directly applies to 15+ problems including:

  • House Robber II (circular array)
  • Delete and Earn
  • Maximum Alternating Subsequence Sum
  • Paint House variations

The "skip adjacent elements" framework is foundational.

Interview frequency​

FAANG Frequency

Appears in Blind 75, NeetCode 150, and Grind 75. Consistently asked at Google, Meta, Amazon, and Microsoft across all interview rounds.

2. Grid/Matrix DP (2D Traversal): Unique Paths​

LeetCode 62 | Medium

Why this problem is essential​

THE canonical introduction to 2D Grid DP. Unique Paths teaches grid traversal with maximum clarity and zero additional complexity. While Minimum Path Sum is also excellent, Unique Paths is the purest form for learning the pattern. It's the foundation problem before tackling any grid-based optimization.

Key insight taught​

2D state space navigation where each cell depends on paths from previous cells:

dp[i][j] = dp[i-1][j] + dp[i][j-1]

Teaches proper boundary condition handling (first row and column initialization) and space optimization from O(m×n) to O(n) using a rolling array.

Also introduces the combinatorial perspective: solvable as C(m+n-2, m-1), teaching multiple solution approaches.

Pattern transferability​

Foundation for 20+ grid DP problems including:

  • Unique Paths II (with obstacles)
  • Minimum Path Sum
  • Triangle
  • Dungeon Game
  • Cherry Pickup

Every grid traversal problem builds on this core pattern.

Interview frequency​

FAANG Frequency

Included in Blind 75 and NeetCode 150. Extremely common in Google, Amazon, and Meta phone screens. Companies often add constraints (obstacles, costs) to test pattern adaptation.

3. Substring/Subsequence DP: Longest Common Subsequence​

LeetCode 1143 | Medium

Why this problem is essential​

The foundational problem for dual-sequence DP patterns. LCS is the teaching problem that unlocks an entire category of string comparison algorithms. It appears in Blind 75, NeetCode 150, and Striver's DP series as the baseline for understanding string DP.

Key insight taught​

The fundamental 2D DP table approach for comparing sequences:

dp[i][j] = dp[i-1][j-1] + 1  (if chars match)
         = max(dp[i-1][j], dp[i][j-1])  (if chars don't match)

Teaches how to build solutions from smaller subproblems across two dimensions and optimize space from 2D to 1D array.

Pattern transferability​

Serves as the template for 20+ related problems including:

  • Edit Distance (the "final boss" of string DP)
  • Longest Palindromic Subsequence
  • Distinct Subsequences
  • Interleaving String

The pattern appears in diff algorithms and bioinformatics applications.

Interview frequency​

FAANG Frequency

Frequently asked at Google, Meta, and Amazon. Considered a "must-solve" baseline for any string DP question. Pattern variations appear consistently across technical screens.

4. Knapsack Variants: Partition Equal Subset Sum​

LeetCode 416 | Medium

Why this problem is essential​

The cleanest representation of the 0/1 knapsack decision framework on LeetCode. This problem reduces the complex partition problem to "can we achieve sum = target?" making the knapsack pattern crystal clear without additional complexity. Featured in NeetCode 150 and multiple FAANG prep lists.

Key insight taught​

Core knapsack decision: "include item" vs "exclude item" with state dp[sum] = achievable or not.

The key optimization is iterating backwards to avoid overwriting:

dp[j] = dp[j] OR dp[j - nums[i]]

Demonstrates space optimization from O(n×sum) to O(sum), a critical knapsack technique.

Pattern transferability​

Directly teaches the subset sum pattern used in 10+ problems:

  • Target Sum (494)
  • Ones and Zeroes (474)
  • Last Stone Weight II
  • Coin Change II (unbounded variant)

The decision framework transfers to all resource allocation problems.

Interview frequency​

FAANG Frequency

Asked repeatedly at Amazon, Google, and Meta. Listed in multiple "most important knapsack problems" compilations. The pattern appears in various disguises across interviews.

5. Interval DP (Partitioning Problems): Burst Balloons​

LeetCode 312 | Hard

Why this problem is essential​

THE canonical problem for interval/partition DP thinking. Burst Balloons requires the counterintuitive insight of choosing "which to burst LAST" rather than first, which is the key revelation that unlocks interval DP. Featured prominently in Striver's DP series as the quintessential interval DP example.

Key insight taught​

The transformative insight: instead of "which to burst first" (creates complex dependencies), think "which to burst LAST" (clean subproblems).

State definition: dp[i][j] = max coins from bursting balloons between i and j

Recurrence: For each partition point k:

dp[i][j] = max(
    dp[i][k-1] +
    nums[i-1] * nums[k] * nums[j+1] +
    dp[k+1][j]
)

Padding the array with 1s handles edge cases elegantly. Time complexity O(n³) is typical for interval DP.

Pattern transferability​

Pattern applies directly to:

  • Matrix Chain Multiplication
  • Stone Game variations
  • Minimum Cost to Merge Stones
  • Minimum Cost Tree From Leaf Values
  • Palindrome Partitioning II

Interview frequency​

Advanced Level

Asked at Google, Amazon, and Meta in senior+ interviews. Often used to differentiate strong from exceptional candidates. The pattern appears when optimization requires trying all partition points.

6. Tree DP: House Robber III​

LeetCode 337 | Medium

Why this problem is essential​

The quintessential tree DP problem taught in virtually every DP curriculum. Perfect progression from linear DP (House Robber I) to tree DP makes the concept crystal clear. Clean problem statement focuses purely on tree DP decision-making without extraneous complexity. Mentioned in AlgoMaster, Labuladong, and multiple FAANG interview guides.

Key insight taught​

State definition on tree nodes: maintain two states for each node (rob this node, don't rob this node).

Bottom-up tree traversal (post-order DFS) processes children before parents to build solutions.

Dependency formula:

rob(node) = node.val + notRob(left) + notRob(right)
notRob(node) = max(rob(left), notRob(left)) +
               max(rob(right), notRob(right))

Teaches memoization on tree structures.

Pattern transferability​

Transfers to problems like:

  • Binary Tree Cameras (968)
  • Maximum Product of Splitted Binary Tree
  • Any problem requiring optimal decisions across tree structures

Interview frequency​

FAANG Frequency

Reported at Amazon (phone and onsite) and Google (phone interviews). Part of standard prep curricula (Educative's Grokking series, AlgoMonster, NeetCode). Perfect difficulty for 45-minute interviews.

7. State Machine DP: Best Time to Buy and Sell Stock with Cooldown​

LeetCode 309 | Medium

Why this problem is essential​

The MOST pedagogical state machine DP problem in the entire stock series. Problem 309 clearly demonstrates explicit state transitions with multiple states (holding, sold, cooldown), making it superior to simpler stock problems for learning. Frequently cited in DP tutorials as the classic state machine example.

Key insight taught​

Finite state machine with explicit states and transitions:

hold[i] = max(hold[i-1], rest[i-1] - prices[i])  // keep holding or buy
sold[i] = hold[i-1] + prices[i]                   // must have held to sell
rest[i] = max(rest[i-1], sold[i-1])              // rest or cooldown after sell

The cooldown constraint teaches how to encode problem constraints into state transitions. This framework generalizes to ALL 6 stock problems (121, 122, 123, 188, 309, 714).

Pattern transferability​

The state machine pattern appears in:

  • Paint House series
  • Problems with transaction limits
  • Any constraint-based decision problem requiring explicit state tracking

Interview frequency​

FAANG Frequency

Included in NeetCode 150. Particularly favored by Google, Meta, and Microsoft for testing DP mastery. Successfully solving this demonstrates strong DP understanding and is used to distinguish mid-level from senior candidates.

8. DP with Optimization: Longest Increasing Subsequence​

LeetCode 300 | Medium

Why this problem is essential​

THE classic problem for teaching DP optimization techniques. LIS has three distinct solutions with different complexities, making it perfect for demonstrating optimization progression. Listed in Blind 75, NeetCode 150, and every major DP guide. Standard interview question at all FAANG companies where follow-ups ask for optimized solutions.

Key insight taught​

Optimization progression:

  1. Naive DP: O(n²) time

    dp[i] = max(dp[j] + 1) for all j < i where nums[i] > nums[j]

  2. Optimized with Binary Search: O(n log n) time

    • Maintain "tails" array where tails[i] is the smallest ending element of all increasing subsequences of length i+1

Critical insight: You don't need the actual subsequence during computation, just track potential endings to enable longer sequences.

Understanding when to use binary search in DP by identifying monotonic properties. Teaches that DP state doesn't always store the final answer, sometimes stores intermediate information for optimal computation.

Pattern transferability​

The binary search optimization technique transfers to multiple DP problems requiring range queries or maintaining sorted auxiliary structures.

Interview frequency​

Optimization Expected

Extremely high frequency across all FAANG. Interviewers expect O(n²) solution initially, then ask for O(n log n) optimization. Tests both DP understanding AND optimization ability.

9. Game Theory DP: Predict the Winner​

LeetCode 486 | Medium

Why this problem is essential​

The standard teaching problem for game theory DP, featured in Labuladong's game theory guide and AlgoMaster patterns. More generalizable than Stone Game (which has a mathematical trick) and cleaner than overcomplicated variants. Perfect difficulty for learning minimax strategy.

Key insight taught​

Core game theory concepts:

State definition: dp[i][j] = maximum score difference (Player 1 - Player 2) for subarray nums[i...j]

Minimax formula:

dp[i][j] = max(
    nums[i] - dp[i+1][j],
    nums[j] - dp[i][j-1]
)

Key insight: Store the DIFFERENCE rather than absolute scores

When you take nums[i], opponent optimally gets dp[i+1][j] advantage, so your net is nums[i] - dp[i+1][j]

Teaches adversarial thinking: each player makes the choice best for themselves, and Player 2's optimal choice minimizes Player 1's advantage (captured by subtraction in recurrence).

Pattern transferability​

Pattern applies to:

  • Stone Game II (1140)
  • Minimum Score After Removals
  • Any 2-player optimal strategy problem

Interview frequency​

FAANG Frequency

Asked at Facebook/Meta according to LeetCode discussions. Standard in game theory sections of interview prep courses. Tests both DP AND strategic thinking simultaneously.

10. Bitmask DP (Complex State): Partition to K Equal Sum Subsets​

LeetCode 698 | Medium

Why this problem is essential​

The most approachable bitmask DP problem for learning the pattern. While Find the Shortest Superstring (943, Hard) is the canonical TSP implementation, problem 698 is better for initial learning at Medium difficulty. Has dedicated "Best for Interviews" solution threads about the bitmask DP approach.

Key insight taught​

State compression fundamentals:

  • Use bitmask to represent which elements are included: dp[mask] = can we partition elements in mask into subsets with target sum
  • Bitmask operations:
    • mask ^ (1 << i) to toggle element
    • mask & (1 << i) to check presence
  • Key insight: Bitmask eliminates redundant permutation checking, reducing n! to n × 2^n
  • Space: O(2^n), only feasible for n ≤ 20 (typically n ≤ 15 in interviews)

Pattern transferability​

Transfers to:

  • TSP problems (943)
  • Maximum Students Taking Exam (1349)
  • Assignment Problems
  • Any problem requiring tracking subsets of elements where n ≤ 15

Interview frequency​

Advanced/Optional

Bitmask DP is relatively rare (less than 5% of FAANG coding rounds), typically appearing in senior-level (L5+/E5+) interviews. Most commonly reported at Amazon. Not included in Blind 75 or NeetCode 150, confirming it's advanced/optional for most candidates.

Study Strategy​

Phase 1: Core Patterns (Problems 1-4)​

Priority Focus

Master these first - they cover 60% of DP interview questions:

  1. House Robber (Linear DP)
  2. Unique Paths (Grid DP)
  3. Longest Common Subsequence (String DP)
  4. Partition Equal Subset Sum (Knapsack)

Phase 2: Advanced Patterns (Problems 5-9)​

After mastering core patterns, tackle these for comprehensive coverage:

  • Burst Balloons (Interval DP)
  • House Robber III (Tree DP)
  • Stock with Cooldown (State Machine)
  • Longest Increasing Subsequence (Optimization)
  • Predict the Winner (Game Theory)

Phase 3: Optional Advanced (Problem 10)​

Study Bitmask DP only after mastering standard patterns, primarily if:

  • Targeting Amazon
  • Applying for senior positions (L5+/E5+)
  • Want comprehensive pattern coverage

Key Insights​

Strategic Mastery Over Exhaustive Coverage​

These ten problems represent force multipliers in DP preparation—each unlocks a family of 10-20+ related problems. The selection prioritizes Medium difficulty (8 of 10) because these problems teach patterns clearly without requiring multiple unrelated advanced techniques.

Burst Balloons (Hard) is included because interval DP requires the complexity to demonstrate the pattern properly.

The Pattern Recognition Mindset​

Critical Understanding

Success in DP interviews comes not from memorizing solutions but from recognizing which pattern applies and understanding the state transition logic.

These ten problems teach you to see the patterns embedded in new problems, turning unfamiliar questions into variations of familiar frameworks.

Focus on Understanding​

Focus on understanding why each solution works, not just how to implement it. For each problem, ask:

  1. What is the state definition?
  2. What is the recurrence relation?
  3. What are the base cases?
  4. Can I optimize the space complexity?
  5. Which other problems use this pattern?

Conclusion​

Mastering these 10 problems provides a comprehensive foundation for dynamic programming interviews at top tech companies. The patterns learned here will transfer to hundreds of related problems, giving you the confidence and ability to tackle unfamiliar DP questions during interviews.

Remember: Pattern recognition + state transition logic = DP mastery 🎯