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.
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).
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.