NeetCode 150 · 2D Dynamic Programming

2D Dynamic Programming Problems

Fill a 2D table where dp[i][j] depends on previous rows/columns. Key patterns: LCS, grid paths, string edit distance, and interval DP.

Problems: 11
Easy: 0
Medium: 7
Hard: 4
Learning approach: Read the problem. Try the test cases yourself first. Click Hint if stuck — it guides without spoiling. Use Show Solution only after a genuine attempt. Then hit Let's Code to run your solution live.
01 Medium MathDP
An m×n grid. Start at top-left, reach bottom-right. Can only move right or down. Count distinct paths.
Test Cases
uniquePaths(3,7) → 28 uniquePaths(3,2) → 3
dp[i][j] = dp[i-1][j] + dp[i][j-1]1D rolling arrayO(m·n)
Each cell can be reached from the cell above or the cell to the left. dp[i][j] = dp[i-1][j] + dp[i][j-1].
Python Solution
def uniquePaths(m, n): dp = [1] * n # first row: all 1s (only one way to reach each cell) for _ in range(m - 1): for j in range(1, n): dp[j] += dp[j - 1] # add paths from the left return dp[-1]
Key idea: Roll a 1D array row by row. The first row is all 1s. For each subsequent row, dp[j] = dp[j] (from above, kept from previous row) + dp[j-1] (from left, just updated).
Time: O(m·n).
Space: O(n).
02 Medium StringDP
Given two strings text1 and text2, return the length of their longest common subsequence.
Test Cases
longestCommonSubsequence('abcde','ace') → 3 longestCommonSubsequence('abc','abc') → 3 longestCommonSubsequence('abc','def') → 0
dp[i][j] match or skipO(m·n)LCS recurrence
If text1[i-1] == text2[j-1], dp[i][j] = 1 + dp[i-1][j-1]. Otherwise, dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
Python Solution
def longestCommonSubsequence(text1, text2): m, n = len(text1), len(text2) 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]: dp[i][j] = dp[i-1][j-1] + 1 else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) return dp[m][n]
Key idea: Classic LCS DP. When characters match, extend the common subsequence. When they don't, take the best result from skipping one character in either string.
Time: O(m·n).
Space: O(m·n).
03 Medium ArrayDPState Machine
After selling, you must wait one day (cooldown) before buying again. Find max profit.
Test Cases
maxProfit([1,2,3,0,2]) → 3 maxProfit([1]) → 0
state machine DPhold/sold/rest statesO(n) O(1)
Define three states: hold (own stock), sold (just sold), rest (cooldown or never bought). Transitions: hold→hold or rest→hold; hold→sold; sold→rest; rest→rest.
Python Solution
def maxProfit(prices): hold = -prices[0] # max profit while holding stock sold = 0 # max profit on day we just sold rest = 0 # max profit on cooldown/rest day for price in prices[1:]: prev_hold = hold hold = max(hold, rest - price) # keep holding or buy from rest rest = max(rest, sold) # keep resting or enter cooldown sold = prev_hold + price # sell today (used prev_hold) return max(sold, rest)
Key idea: State machine with three states. Each day, compute the max profit in each state based on yesterday's values. The answer is the max of sold and rest on the last day.
Time: O(n).
Space: O(1).
04 Medium ArrayDP
Return the number of combinations (not permutations) that make up the amount using given coins.
Test Cases
change(5, [1,2,5]) → 4 # 5, 2+2+1, 2+1+1+1, 1+1+1+1+1 change(3, [2]) → 0
unbounded knapsackcoin outer loopO(amount·coins)
Process coins as the outer loop (to count combinations not permutations). dp[i] += dp[i - coin] for each coin.
Python Solution
def change(amount, coins): dp = [0] * (amount + 1) dp[0] = 1 # one way to make amount 0: use no coins for coin in coins: # outer loop = coins (ensures combinations) for i in range(coin, amount + 1): dp[i] += dp[i - coin] return dp[amount]
Key idea: Unbounded knapsack. Processing coins in the outer loop ensures each combination is counted once (no permutations). dp[i] = sum of ways to reach i using all coins processed so far.
Time: O(amount·coins).
Space: O(amount).
05 Medium ArrayDPDFSBacktracking
Given nums and target, assign + or - to each number. Count ways to reach the target sum.
Test Cases
findTargetSumWays([1,1,1,1,1], 3) → 5 findTargetSumWays([1], 1) → 1
dp dict of sumsO(n·sum)add/subtract each num
Use a dictionary mapping sum → count. For each number, create a new dict by adding and subtracting the number from all existing sums.
Python Solution
def findTargetSumWays(nums, target): dp = {0: 1} # sum → number of ways to reach that sum for n in nums: new_dp = {} for s, count in dp.items(): new_dp[s + n] = new_dp.get(s + n, 0) + count new_dp[s - n] = new_dp.get(s - n, 0) + count dp = new_dp return dp.get(target, 0)
Key idea: DP with a dictionary of reachable sums. For each number, every existing sum branches into two new sums (add or subtract). This naturally handles the exponential combinations efficiently.
Time: O(n·sum).
Space: O(sum).
06 Medium StringDP
Return True if s3 is formed by interleaving s1 and s2 (maintaining relative order in both).
Test Cases
isInterleave('aabcc','dbbca','aadbbcbcac') → True isInterleave('aabcc','dbbca','aadbbbaccc') → False
dp[i][j] = s3[i+j-1] matchesO(m·n)1D optimization
dp[i][j] = can s3[0:i+j] be formed from s1[0:i] and s2[0:j]? Transition: either take from s1 or s2.
Python Solution
def isInterleave(s1, s2, s3): m, n = len(s1), len(s2) if m + n != len(s3): return False dp = [[False] * (n + 1) for _ in range(m + 1)] dp[0][0] = True for i in range(1, m + 1): dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1] for j in range(1, n + 1): dp[0][j] = dp[0][j-1] and s2[j-1] == s3[j-1] for i in range(1, m + 1): for j in range(1, n + 1): dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[i+j-1]) or (dp[i][j-1] and s2[j-1] == s3[i+j-1]) return dp[m][n]
Key idea: dp[i][j] = whether s1[0:i] and s2[0:j] can interleave to form s3[0:i+j]. At each cell, try using the next char from s1 or s2.
Time: O(m·n).
Space: O(m·n).
07 Hard ArrayDFSDPMemoization
Given m×n integer matrix, find the length of the longest strictly increasing path. You can move in 4 directions.
Test Cases
longestIncreasingPath([[9,9,4],[6,6,8],[2,1,1]]) → 4 # [1,2,6,9] longestIncreasingPath([[3,4,5],[3,2,6],[2,2,1]]) → 4
DFS + lru_cache memoizationno cycle possibleO(m·n)
DFS from each cell. Since we require strictly increasing values, no revisit is possible — safe to memoize without a visited set.
Python Solution
from functools import lru_cache def longestIncreasingPath(matrix): rows, cols = len(matrix), len(matrix[0]) @lru_cache(maxsize=None) def dfs(r, c): best = 1 for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]: nr, nc = r+dr, c+dc if (0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]): best = max(best, 1 + dfs(nr, nc)) return best return max(dfs(r, c) for r in range(rows) for c in range(cols))
Key idea: DFS with memoization. Since we only move to strictly larger values, the graph is a DAG — no cycles. Memoize each cell's result. The answer is the max over all starting cells.
Time: O(m·n).
Space: O(m·n).
08 Hard StringDP
Given strings s and t, return the number of distinct subsequences of s which equals t.
Test Cases
numDistinct('rabbbit','rabbit') → 3 numDistinct('babgbag','bag') → 5
dp[i][j] countmatch adds dp[i-1][j-1]O(m·n)
dp[i][j] = ways s[0:i] contains t[0:j] as a subsequence. If s[i-1]==t[j-1], include matches + non-matches.
Python Solution
def numDistinct(s, t): m, n = len(s), len(t) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(m + 1): dp[i][0] = 1 # empty t is always a subsequence for i in range(1, m + 1): for j in range(1, n + 1): dp[i][j] = dp[i-1][j] # skip s[i-1] if s[i-1] == t[j-1]: dp[i][j] += dp[i-1][j-1] # match s[i-1] with t[j-1] return dp[m][n]
Key idea: dp[i][j] = ways to match t[0:j] in s[0:i]. Always add the option of skipping s[i-1]. When s[i-1]==t[j-1], also add the option of matching them.
Time: O(m·n).
Space: O(m·n).
09 Medium StringDP
Given two words, find the minimum number of operations (insert, delete, replace) to convert word1 to word2.
Test Cases
minDistance('horse','ros') → 3 minDistance('intention','execution') → 5
dp edit distancespace-optimized 1DO(m·n)
dp[i][j] = min edits to convert word1[0:i] to word2[0:j]. Three operations: insert, delete, replace.
Python Solution
def minDistance(word1, word2): m, n = len(word1), len(word2) dp = list(range(n + 1)) # base case: convert empty to word2 prefixes for i in range(1, m + 1): prev = dp[0] dp[0] = i # base case: convert word1 prefix to empty for j in range(1, n + 1): temp = dp[j] if word1[i-1] == word2[j-1]: dp[j] = prev # no edit needed else: dp[j] = 1 + min( prev, # replace dp[j], # delete from word1 dp[j-1] # insert into word1 ) prev = temp return dp[n]
Key idea: Classic edit distance DP. Three choices: replace (diagonal), delete from word1 (above), insert (left). Space-optimized to 1D by carrying a prev variable.
Time: O(m·n).
Space: O(n).
10 Hard ArrayDP
n balloons indexed 0 to n-1, nums[i] is the number. Bursting balloon i gives nums[i-1]*nums[i]*nums[i+1] coins. Find maximum coins from bursting all balloons.
Test Cases
maxCoins([3,1,5,8]) → 167 maxCoins([1,5]) → 10
interval DPlast balloon in intervalO(n³)
Think of 'k' as the last balloon to burst in interval [left, right]. Add 1s to both ends of nums as sentinels.
Python Solution
def maxCoins(nums): nums = [1] + nums + [1] # add sentinel 1s n = len(nums) dp = [[0] * n for _ in range(n)] for length in range(2, n): for left in range(0, n - length): right = left + length for k in range(left + 1, right): # k is the LAST balloon burst in (left, right) coins = nums[left] * nums[k] * nums[right] dp[left][right] = max( dp[left][right], coins + dp[left][k] + dp[k][right] ) return dp[0][n-1]
Key idea: Interval DP. Think of k as the LAST balloon burst in interval (left, right) — this avoids tracking which balloons are already gone. The coins from k use nums[left]*nums[k]*nums[right] since all others in the interval are gone.
Time: O(n³).
Space: O(n²).
11 Hard StringDPRecursion
Implement regular expression matching with '.' (any char) and '*' (zero or more of preceding). The whole string must match.
Test Cases
isMatch('aa','a') → False isMatch('aa','a*') → True isMatch('ab','.*') → True
dp[i][j] match state'*' dual caseO(m·n)
dp[i][j] = does s[0:i] match p[0:j]? For '*', either use it as zero occurrences (dp[i][j-2]) or one more (dp[i-1][j] if char matches).
Python Solution
def isMatch(s, p): m, n = len(s), len(p) dp = [[False] * (n + 1) for _ in range(m + 1)] dp[0][0] = True # Handle patterns like a*, a*b*, etc. matching empty string for j in range(1, n + 1): if p[j-1] == '*': dp[0][j] = dp[0][j-2] for i in range(1, m + 1): for j in range(1, n + 1): if p[j-1] == '*': dp[i][j] = dp[i][j-2] # '*' = zero occurrences if p[j-2] == '.' or p[j-2] == s[i-1]: dp[i][j] |= dp[i-1][j] # '*' = one more occurrence elif p[j-1] == '.' or p[j-1] == s[i-1]: dp[i][j] = dp[i-1][j-1] return dp[m][n]
Key idea: dp[i][j] = s[0:i] matches p[0:j]. For '*': zero occurrences (dp[i][j-2]) or one more (dp[i-1][j] if the char before '*' matches). For '.': matches any single char.
Time: O(m·n).
Space: O(m·n).
← Prev Category Next Category →