Grid optimization, 0/1 knapsack, and dual string alignments
Solve problems with two independent dimensions (e.g. two strings, grid cells, or items vs capacity) by filling an M × N table where dp[i][j] transitions from adjacent predecessors.
Core Invariant: Table grid invariant: Every cell `dp[i][j]` is derived from `dp[i-1][j]` (delete/skip first), `dp[i][j-1]` (insert/skip second), or `dp[i-1][j-1]` (match/replace both). Base row `i=0` and col `j=0` define boundary conditions.
Greedy works (e.g. Fractional Knapsack), or dimensions are sparse with massive bounds (use memoized recursion).
def longest_common_subsequence(text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
# dp[i][j] = LCS length between text1[:i] and text2[:j]
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
# Characters match: extend diagonal subsequence
dp[i][j] = 1 + dp[i - 1][j - 1]
else:
# Discard either char from text1 or text2
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]# | 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% | ||
| #70 | Climbing Stairs MathDynamic ProgrammingMemoization | Easy | 100% | 54.2% | ||
| #198 | House Robber ArrayDynamic Programming | Medium | 100% | 53.4% | ||
| #55 | Jump Game ArrayDynamic ProgrammingGreedy | Medium | 100% | 41.2% | ||
| #300 | Longest Increasing Subsequence ArrayBinary SearchDynamic ProgrammingLongest Increasing Subsequence | Medium | 100% | 59.7% | ||
| #45 | Jump Game II ArrayDynamic ProgrammingGreedy | Medium | 100% | 0.4% | ||
| #91 | Decode Ways StringDynamic Programming | Medium | 100% | 0.4% | ||
| #124 | Binary Tree Maximum Path Sum Dynamic ProgrammingTreeDepth-First SearchBinary TreeDP on Trees | Hard | 100% | 42.5% | ||
| #122 | Best Time to Buy and Sell Stock II ArrayDynamic ProgrammingGreedy | Medium | 100% | 71.3% | ||
| #221 | Maximal Square ArrayDynamic ProgrammingMatrix | Medium | 100% | 50.6% | ||
| #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% | 42.2% | ||
| #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% | 0.6% | ||
| #416 | Medium | 100% | 49.7% | |||
| #44 | Wildcard Matching StringDynamic ProgrammingGreedyRecursion | Hard | 100% | 0.3% | ||
| #118 | Pascal's Triangle ArrayDynamic Programming | Easy | 100% | 79.1% | ||
| #312 | Burst Balloons ArrayDynamic Programming | Hard | 100% | 63.9% | ||
| #140 | Word Break II ArrayHash TableStringDynamic ProgrammingBacktrackingTrieMemoization | Hard | 100% | 0.6% | ||
| #354 | Russian Doll Envelopes ArrayBinary SearchDynamic ProgrammingSortingLongest Increasing Subsequence | Hard | 100% | 38.0% | ||
| #509 | Fibonacci Number MathDynamic ProgrammingRecursionMemoization | Easy | 100% | 74.3% | ||
| #64 | Minimum Path Sum ArrayDynamic ProgrammingMatrix | Medium | 100% | 68.5% | ||
| #1048 | Longest String Chain ArrayHash TableTwo PointersStringDynamic ProgrammingSorting | Medium | 100% | 63.3% | ||
| #968 | Binary Tree Cameras Dynamic ProgrammingTreeDepth-First SearchBinary TreeDP on Trees | Hard | 100% | 0.5% | ||
| #392 | Is Subsequence Two PointersStringDynamic Programming | Easy | 88% | 49.2% | ||
| #85 | Maximal Rectangle ArrayDynamic ProgrammingStackMatrixMonotonic Stack | Hard | 83% | 59.2% | ||
| #518 | Coin Change II ArrayDynamic ProgrammingKnapsack ProblemComplete Knapsack | Medium | 100% | 59.6% | ||
| #115 | Hard | 100% | 52.2% | |||
| #516 | Longest Palindromic Subsequence StringDynamic Programming | Medium | 69% | 65.7% | ||
| #907 | Sum of Subarray Minimums ArrayDynamic ProgrammingStackMonotonic Stack | Medium | 88% | 38.8% | ||
| #123 | Best Time to Buy and Sell Stock III ArrayDynamic Programming | Hard | 82% | 54.2% | ||
| #1326 | Minimum Number of Taps to Open to Water a Garden ArrayDynamic ProgrammingGreedy | Hard | 100% | 51.0% | ||
| #542 | 01 Matrix ArrayDynamic ProgrammingBreadth-First SearchMatrix | Medium | 100% | 54.4% | ||
| #465 | Optimal Account Balancing ArrayDynamic ProgrammingBacktrackingBit ManipulationBitmask | Hard | 100% | 50.5% | ||
| #983 | Minimum Cost For Tickets ArrayDynamic Programming | Medium | 100% | 0.7% | ||
| #740 | Delete and Earn ArrayHash TableDynamic Programming | Medium | 100% | 57.4% | ||
| #131 | Palindrome Partitioning StringDynamic ProgrammingBacktracking | Medium | 100% | 74.3% |
Browse company-specific interview problem lists and recency breakdowns:
Master core algorithmic patterns tested in FAANG & Big Tech coding interviews.
Grid optimization, 0/1 knapsack, and dual string alignments It is categorized under Advanced & DP and features 562 curated interview problems across Easy (13), Medium (280), and Hard (269) difficulties.
Companies frequently asking 2D Dynamic Programming & Knapsack 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.