[Leetcode Pattern] Dynamic Programming

A cheet sheet of dp problems in leetcode.

Determinate factors (one dimension)

dp[i] can be deduced by dp[x] where x<i. Assign base value for top elms and use the base to get the rest within a loop.

e.g. Climbing Stair

# dp[i] represents total ways to reach i
dp = [0] * n
dp[0] = 1
dp[1] = 2
for i in range(2, n): dp[i] = dp[i-1] + dp[i-2]

e.g. Counting Bits

# dp[i] represents target value of i
dp = [0] * (n+1)
dp[1] = 1
for i in range(2, n+1): dp[i] = dp[i//2]+i%2

e.g. Decode Ways

# dp[i] represents total ways to reach i
dp = [0] * (n+1)
dp[0] = 1
for i in range(1, n+1): # to filter zero, break the update to two steps
    if s[i-1]!='0': dp[i] += dp[i-1]
    if i!=1 and '09'<s[i-2:i]<='26': dp[i] += dp[i-2]

Indeterminate factors (one dimension)

dp[i] may be updated by a list of dp[i-x]s where x<i. Assign base value for top elms. Use nested for loop to traverse each candidate derived from x to accordingly update i.

e.g. Coin Change

# dp[i] represents least number of coins to compose this i
unreachable = amount + 1 # use a val to indicate if i is composable
dp = [unreachable] * unreachable 
dp[0] = 0 # base for each candidate used singly
for i in range(1, unreachable): 
# 0-> i-coin -> i
# dp[i-coin] from 0 to i-coin if i-coin is computed
# 1 from i-coin to i as coin provides a valid path
    for coin in coins:  
        if dp[i-coin]!=unreachable and i>=coin: 
            dp[i] = min([dp[i], 1+dp[i-coin]])

e.g. Longest Increasing Subsequence

# dp[i] represents max @ i so far
dp = [1] * n
for i in range(1, n):
    currMax = 1
    for j in range(i): # backtracking        
        if nums[i]>nums[j]: # check if nums[i] permits enlarging subsequence
            currMax = max([currMax, 1+dp[j]]) # consider dp[j] as helper
        dp[i] = currMax

Determinate factors (2 one dimension)

dp1[i] / dp2[i] can only be known with existence of dp1[x] & dp2[x] where x<i. Assign base value for top elms and use the base to get the rest within a loop.

e.g. Best Time to Buy and Sell Stock with Cooldown

# sell[i] represents max prft without holding 
# hold[i] represents max prft with holding
sell = [0]*n
hold = [0]*n 
hold[0] = -prices[0]
for i in range(1, n):
    sell[i] = max(sell[i-1], hold[i-1]+prices[i])
    hold[i] = max(hold[i-1], (sell[i-2] if i>=2 else 0) - prices[i])

Determinate factors (two dimensions)

2 factor affects the variant like start/end, row/col. Hence, dp[i][j] explains the variant more clearly.

e.g. Palindromic Substrings

# dp[start][end]represents if s[start:1+end] is a palindrome
dp = [[False] * n for _ in range(n)]
for l in range(1, n+1): # 1 ~ n possible length of substring
    for start in range(n-l+1): # 0 ~ n-l
        # make a sliding window of len l
        end = start+l-1 # l-1 ~ n-1
        # check if this window is palindrome
        if l==1 or \
        (l==2 and s[start]==s[end]) or \
        (l>=3 and dp[start+1][end-1] and s[start]==s[end]): 
            dp[start][end] = True
            res+=1