Dynamic Programming

Publish on: Classify at:
Words: 1124 Read:≈ 6mins Views:

Ling Shen Problem List

Linear DP

Alt text

10. Regular Expression Matching

dp[i][j] indicates if s(0,i-1) matches p(0,j-1)

Base case: s empty, p empty → True; s empty, p xx type → True Compare s[i], p[j]: if not match and p[j] is *, and s[i] matches p[j-1], three possibilities: match one letter, zero letters, multiple letters. If not match and p[j] is *, and s[i] doesn’t match p[j-1], check zero letter option.

LC 377: Combination Sum IV

Difference from complete knapsack: [1,3],[3,1] count as different answers. Similar to permutation backtracking. If using @cache decorator, cannot use global variable res; must return res from dfs.

LC 139: Word Break “leetcode” can be composed from “leet” and “code”. If “code” in wordSet, then dp[9]=dp[4]

Beginner DP

House Robber

LC 198

Space optimization.

213 House Robber II

Houses in circle. Consider robbing first n-1 houses only, and last n-1 houses only, since first and last cannot be robbed together!

740. Delete and Earn

If choose x, delete and earn points, all x+1 and x-1 get deleted, so delete all other x and earn points. Choose x → earn x*cnt[x], cannot earn x+1/x-1 points.

Maximum Subarray Sum

LC 53

dp[i] stores maximum sum ending at current element

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

Space optimization:

1
2

f=max(x, f+x)
res=max(f, res)

LC 1749 Maximum Absolute Sum of Any Subarray

Maintain maximum and minimum sums ending at current element. Absolute maximum → maximum or minimum subarray sum.

Grid DP

Basic: 63. Unique Paths II

dp[i+1][j+1] represents number of paths to grid[i][j]. Initialize dp[0][1]=1

329. Longest Increasing Path in Matrix

Memoized search, dfs(i,j) starts from this cell, searches surroundings, finds longest path length, stores in dp[i][j]

0/1 Knapsack

LC 494 Target Sum

Memoized search: select exactly k items to reach capacity c, count ways. Recursion backward, DP rewrites as forward traversal.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        n=len(nums)
        s=sum(nums)
        p=(target+s)//2
        if (target+s)%2!=0 or target+s<0:
            return 0

        f=[[0]*(p+1) for _ in range(n+1)]
        f[0][0]=1
        for i, x in enumerate(nums):
            for c in range(p+1):
                if c>=x:
                    f[i+1][c]=f[i][c]+f[i][c-x]
                else:
                    f[i+1][c]=f[i][c]
        return f[n][p]

LC 3180 Maximum Total Reward

Array rewardValues, length n. Initial reward x=0, all indices unmarked. Operation: choose unmarked index i, if rewardValues[i] > current x, add to x and mark i. Return maximum total reward.

dp[i][j] indicates if sum j achievable from first i items.

Complete Knapsack

n items, volume w[i], value v[i], each selectable infinitely, capacity c, maximize value. dfs(i, c)=dfs(i-1, c)+dfs(i, c-w[i])

LC 322 Coin Change

Coin value as volume, each value=1. amount as capacity, find minimum value when volume exactly equals capacity.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def coinChange(self, coins: List[int], amount: int) -> int:
    #dfs(i, c): minimum coins needed at coin i, total value c
    @cache
    def dfs(i, c):
        if i<0:
            return 0 if c==0 else inf #capacity must exactly equal amount
        if coins[i]>c:
            return dfs(i-1, c)
        return min(dfs(i-1, c), dfs(i, c-coins[i])+1)
    res=dfs(len(coins)-1, amount)
    return res if res<inf else -1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def coinChange(self, coins: List[int], amount: int) -> int:
    n=len(coins)
    dp=[[inf]*(amount+1) for _ in range(n+1)]
    dp[0][0]=0
    for i, x in enumerate(coins):
        for j in range(amount+1):
            if x<=j:
                dp[i+1][j]=min(dp[i+1][j-x]+1, dp[i][j])            
            else:
                dp[i+1][j]=dp[i][j]
    return dp[n][amount] if dp[n][amount]<inf else -1

Longest Common Subsequence

LC 1143

dfs(i, j) length of LCS up to s[i] and t[j].

  1. s[i]==t[j] → must select dfs(i, j)=dfs(i-1, j-1)+1
  2. s[i]!=t[j] dfs(i, j)=max(dfs(i, j-1), dfs(i-1, j))

LC 72 Edit Distance

dfs(i, j) operations needed to make s[0:i] and t[0:j] identical.

s: rorse, t: rose Delete from S → dfs(i, j)=dfs(i-1, j)+1

s: ct, t: cat Add to S → dfs(0, 0)=0, dfs(0, 1)=dfs(0, 0)+1=1 dfs(i, j)=dfs(i, j-1)+1

Replace in S → dfs(i, j)=dfs(i-1, j-1)+1

When s[i]!=t[j]: dfs(i, j)=min(dfs(i-1, j), dfs(i, j-1), dfs(i-1, j-1))+1

Note boundaries: dp[0][0]=0, dp[i][0]=i, dp[0][j]=j. Initialize (m+1)*(n+1) matrix, dp[i][j] for word1[i] and word2[j] (word1[i+1], word2[j+1])

LC 3290 Maximum Score from Arrays

a = [3,2,5,6], b = [2,-6,4,-5,-3,2,-7] Start from last element of b.

If select: consider max product of [3,2,5] and [2,-6,…,2] If not select: consider max product of [3,2,5,6] and [2,-6,…,2]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def maxScore(self, a: List[int], b: List[int]) -> int:
    #dp[i][j]=max(dp[i][j-1], dp[i-1][j-1]+a[i-1]*b[j-1])
    m=len(a)
    n=len(b)
    dp=[[-inf]*(n+1) for _ in range(m+1)]
    dp[0]=[0]*(n+1)
    for i in range(m):
        for j in range(n):
            dp[i+1][j+1]=max(dp[i+1][j], dp[i][j]+a[i]*b[j])
    return dp[m][n]
    #dp[1][2]=max(dp[1][1], dp[0][1]+a[0]*b[1])

Initialize dp[0]=[0]*(n+1) because when array a not started (i=0), product sum=0 regardless of b.

Interval DP

State transition: from center outward, i backward, j forward.

516. Longest Palindromic Subsequence: select/not select 

1
2
3
4

if s[i]==s[j]:
    dfs(i, j)=dfs(i+1, j-1)+2
else:
    dfs(i, j)=max(dfs(i+1, j), dfs(i, j-1))

Note traversal order:

1
2
3

for i in range(n-1, -1, -1):
    dp[i][i]=1
    for j in range(i+1, n):

5. Longest Palindromic Substring

dp[i][j] indicates if s[i:j+1] is palindrome. dp[i][j]=dp[i-1][j+1] and s[i]==s[j] So i backward, j forward.

1039. Minimum Score Triangulation of Polygon

Interval DP spreads from center.

1

dp[i][j]=values[i]*values[j]*values[k]+dp[i][k]+dp[k][j]

Initialize dp: recursive base case. For i,k,j=0,1,2, dp[i][k] must be 0. So all dp[i][i+1]=0.

Longest Increasing Subsequence

Backtrack → memoized search → DP Greedy + binary search optimal.

Graph DP

787. Cheapest Flights Within K Stops

dp[t][i] minimum cost to reach city i with t-1 transfers. Simulate transfers: iterate transfer counts 0 to k, each time traverse all flights to update minimum cost to reach each destination with exactly x transfers.

State Machine DP

Define f[i][j] optimal value for prefix a[:i] in state j. j usually small.

123. Best Time to Buy and Sell Stock III

#0: no operation, 1: first hold, 2: first not hold, 3: second hold, 4: second not hold

Partition DP

139. Word Break

dp[i+1] indicates if string s(0,j) can be composed from dictionary. For each end i, enumerate start j, check if s[j:i+1] in dictionary and dp[j]==True

91. Decode Ways

dp[i+1] number of ways to decode s(0,i)

If s[i] can be second digit of two-digit number, dp[i+1]+=dp[i-1] If s[i]>0, dp[i+1]+=dp[i]

State Compression

Stage 1: Basic Space Optimization (Interview Essential)

✅ LC 70. Climbing Stairs ✅ LC 198. House Robber ✅ LC 213. House Robber II ✅ LC 121. Best Time to Buy and Sell Stock ✅ LC 123. Best Time to Buy and Sell Stock III ✅ LC 322. Coin Change ✅ LC 518. Coin Change 2

Stage 2: State Compression Intro (Interview Plus)

🔥 LC 62. Unique Paths 🔥 LC 63. Unique Paths II 🔥 LC 64. Minimum Path Sum 🔥 LC 120. Triangle 🔥 LC 221. Maximal Square

Stage 3: Advanced State Compression (Senior Interview)

💪 LC 139. Word Break 💪 LC 300. Longest Increasing Subsequence 💪 LC 72. Edit Distance 💪 LC 97. Interleaving String 💪 LC 312. Burst Balloons 💪 LC 416. Partition Equal Subset Sum