Linear recurrence relations, state machines, and optimal decision subproblems
Break a sequential decision problem into overlapping subproblems governed by a recurrence relation dp[i] = f(dp[i-1], dp[i-2], ...), caching intermediate states to avoid exponential recomputation.
Core Invariant: State definition must capture all information needed for future transitions. E.g., `dp[i]` = best answer considering elements up to `i`. Once `dp[i]` is computed, prior steps never need re-evaluation.
Decisions have circular dependencies or no optimal substructure (e.g. past decisions invalidate state without being captured in state index).
def rob(nums: list[int]) -> int:
if not nums:
return 0
if len(nums) == 1:
return nums[0]
# State: dp[i] = max money robbing from house 0..i
# Transition: dp[i] = max(dp[i-1], dp[i-2] + nums[i])
# Space optimized: only need previous two values
prev2 = nums[0]
prev1 = max(nums[0], nums[1])
for i in range(2, len(nums)):
curr = max(prev1, prev2 + nums[i])
prev2 = prev1
prev1 = curr
return prev1# | Problem | Difficulty | Top Companies↓ | Frequency | Acceptance | |
|---|---|---|---|---|---|---|
| #121 | Best Time to Buy and Sell Stock ArrayDynamic Programming | Easy | 100% | 57.0% | ||
| #5 | Longest Palindromic Substring Two PointersStringDynamic ProgrammingManacher | Medium | 100% | 38.2% | ||
| #42 | Trapping Rain Water ArrayTwo PointersDynamic ProgrammingStackMonotonic Stack | Hard | 100% | 67.7% | ||
| #53 | Maximum Subarray ArrayDivide and ConquerDynamic Programming | Medium | 100% | 53.5% | ||
| #322 | Medium | 100% | 48.7% | |||
| #198 | House Robber ArrayDynamic Programming | Medium | 100% | 53.4% | ||
| #70 | Climbing Stairs MathDynamic ProgrammingMemoization | Easy | 100% | 54.2% | ||
| #22 | Generate Parentheses StringDynamic ProgrammingBacktrackingBracket Sequences | Medium | 100% | 78.9% | ||
| #55 | Jump Game ArrayDynamic ProgrammingGreedy | Medium | 100% | 41.2% | ||
| #139 | Word Break ArrayHash TableStringDynamic ProgrammingTrieMemoizationBrute-Force Search | Medium | 100% | 49.6% | ||
| #300 | Longest Increasing Subsequence ArrayBinary SearchDynamic ProgrammingLongest Increasing Subsequence | Medium | 100% | 59.7% | ||
| #45 | Medium | 100% | 43.1% | |||
| #122 | Best Time to Buy and Sell Stock II ArrayDynamic ProgrammingGreedy | Medium | 100% | 71.3% | ||
| #221 | Maximal Square ArrayDynamic ProgrammingMatrix | Medium | 100% | 0.5% | ||
| #91 | Decode Ways StringDynamic Programming | Medium | 100% | 38.2% | ||
| #124 | Binary Tree Maximum Path Sum Dynamic ProgrammingTreeDepth-First SearchBinary TreeDP on Trees | Hard | 100% | 42.5% | ||
| #647 | Palindromic Substrings Two PointersStringDynamic Programming | Medium | 100% | 73.0% | ||
| #10 | Regular Expression Matching StringDynamic ProgrammingRecursion | Hard | 100% | 31.2% | ||
| #152 | Maximum Product Subarray ArrayDynamic Programming | Medium | 100% | 36.7% | ||
| #32 | Longest Valid Parentheses StringDynamic ProgrammingStackBracket Sequences | Hard | 100% | 39.1% | ||
| #72 | Edit Distance StringDynamic Programming | Medium | 77% | 60.9% | ||
| #62 | Unique Paths MathDynamic ProgrammingCombinatorics | Medium | 67% | 67.0% | ||
| #410 | Split Array Largest Sum ArrayBinary SearchDynamic ProgrammingGreedyPrefix Sum | Hard | 100% | 60.9% | ||
| #1235 | Maximum Profit in Job Scheduling ArrayBinary SearchDynamic ProgrammingSorting | Hard | 100% | 54.8% | ||
| #1143 | Longest Common Subsequence StringDynamic ProgrammingLongest Common Subsequence | Medium | 88% | 59.3% | ||
| #787 | Cheapest Flights Within K Stops Dynamic ProgrammingDepth-First SearchBreadth-First SearchGraph TheoryHeap (Priority Queue)Shortest Path | Medium | 100% | 0.4% | ||
| #435 | Non-overlapping Intervals ArrayDynamic ProgrammingGreedySorting | Medium | 90% | 57.4% | ||
| #213 | House Robber II ArrayDynamic Programming | Medium | 78% | 45.2% | ||
| #678 | Valid Parenthesis String StringDynamic ProgrammingStackGreedyBracket Sequences | Medium | 100% | 40.3% | ||
| #329 | Longest Increasing Path in a Matrix ArrayDynamic ProgrammingDepth-First SearchBreadth-First SearchGraph TheoryTopological SortMemoizationMatrixDirected Acyclic Graph | Hard | 93% | 56.8% | ||
| #44 | Wildcard Matching StringDynamic ProgrammingGreedyRecursion | Hard | 100% | 32.3% | ||
| #416 | Partition Equal Subset Sum ArrayDynamic ProgrammingKnapsack Problem0-1 Knapsack | Medium | 100% | 0.5% | ||
| #312 | Burst Balloons ArrayDynamic Programming | Hard | 100% | 63.9% | ||
| #140 | Word Break II ArrayHash TableStringDynamic ProgrammingBacktrackingTrieMemoization | Hard | 100% | 55.8% | ||
| #118 | Pascal's Triangle ArrayDynamic Programming | Easy | 100% | 0.8% | ||
| #354 | Russian Doll Envelopes ArrayBinary SearchDynamic ProgrammingSortingLongest Increasing Subsequence | Hard | 100% | 0.4% | ||
| #509 | Fibonacci Number MathDynamic ProgrammingRecursionMemoization | Easy | 100% | 74.3% | ||
| #64 | Minimum Path Sum ArrayDynamic ProgrammingMatrix | Medium | 100% | 68.5% | ||
| #968 | Binary Tree Cameras Dynamic ProgrammingTreeDepth-First SearchBinary TreeDP on Trees | Hard | 100% | 48.0% | ||
| #1048 | Longest String Chain ArrayHash TableTwo PointersStringDynamic ProgrammingSorting | Medium | 100% | 63.3% | ||
| #392 | Is Subsequence Two PointersStringDynamic Programming | Easy | 88% | 0.5% | ||
| #85 | Maximal Rectangle ArrayDynamic ProgrammingStackMatrixMonotonic Stack | Hard | 83% | 0.6% | ||
| #518 | Coin Change II ArrayDynamic ProgrammingKnapsack ProblemComplete Knapsack | Medium | 100% | 59.6% | ||
| #115 | Distinct Subsequences StringDynamic Programming | Hard | 100% | 52.2% | ||
| #516 | Longest Palindromic Subsequence StringDynamic Programming | Medium | 69% | 65.7% | ||
| #907 | Sum of Subarray Minimums ArrayDynamic ProgrammingStackMonotonic Stack | Medium | 88% | 0.4% | ||
| #123 | Best Time to Buy and Sell Stock III ArrayDynamic Programming | Hard | 82% | 0.5% | ||
| #465 | Optimal Account Balancing ArrayDynamic ProgrammingBacktrackingBit ManipulationBitmask | Hard | 100% | 0.5% | ||
| #1326 | Minimum Number of Taps to Open to Water a Garden ArrayDynamic ProgrammingGreedy | Hard | 100% | 51.0% | ||
| #131 | Palindrome Partitioning StringDynamic ProgrammingBacktracking | Medium | 100% | 0.7% |
Browse company-specific interview problem lists and recency breakdowns:
Master core algorithmic patterns tested in FAANG & Big Tech coding interviews.
Linear recurrence relations, state machines, and optimal decision subproblems It is categorized under Advanced & DP and features 561 curated interview problems across Easy (14), Medium (280), and Hard (267) difficulties.
Companies frequently asking 1D Dynamic Programming questions include Google, Amazon, Microsoft, Meta, Bloomberg, Infosys.
Start by studying the algorithmic strategy and template code, then practice Easy and Medium problems before attempting Hard problems under timed conditions.