Dynamic Programming

Posted on Edited on In ,

Overview

Sometimes normal recursive method will cost a lot of time and not very efficient. In these cases, the DP(Dynamic Programming) can be a good choice. The key of DP is to record the previous solutions.

If a problem has two featrues:

  • Optimal Substructure
    • The solution of a problem depends on the solution of its subproblem
  • Overlapping subproblem
    • The subproblem needs to be used several times when dealing with the main problem
      Then we can think about using DP.

Two forms

There are two main ways to do DP. The bottom-up is the most common DP method.

Top-down(recursion with memory)

Establish a memory data structure(like a list) to store the previous values, avoiding the repeat calculation on that value.

Bottom-up(real DP)

Iterate from the bottom. This is better than the previous one because there is no recursive thus no extra cost.

Template

I felt DP is like a 2-demensional array, which can be reduced to a 1-D array. Usually the row i means the action at step i; the column j means a similar result to the original question.

1
2
3
4
5
6
dp = [[.. for i in range(m)] for j in range(n)] # Create 
dp[0][0] = ...    # init
for i in ...
    for j in ...
        dp[i][j] = ...	# transition
return dp[x][y]

Models

Linear Model

SubArray

dp[i] means subarray s[:i] and you must use s[i-1], return max(dp)

No.53 - Max sum subarray

1
2
3
4
5
if dp[i - 1] > 0:
    dp[i] = dp[i-1] + nums[i]
else:
    dp[i] = nums[i]
return max(dp)

No.300 - Longest Increasing Subsequence

No.152 - Maximum Product Subarray
dp1 contains the max product; dp2 contains the min product

List from 0 to i

dp[i] means s[:i], return dp[len(s)]

No.139 - Word Break

No.91 - Decode Ways

No.70 - Climbing Stairs

No.279 - Perfect Squares

No.62 - Unique Paths

Interval Model

The problem can be described as p[i, j]

Palindromic Substring

No.5 - Longest Palindromic Substring
dp[i][j] means wether s[i: j + 1] is a palindromic substring

1
2
3
4
5
6
7
8
9
for i in range(len(s)):
    dp[i][i] = True

for i in range(len(s), -1, -1):
    for j in range(i, len(s)):
        if i + 1 > j - 1:
            dp[i][j] = dp[i][j] or s[i] == s[j]
        else:
            dp[i][j] = dp[i][j] or dp[i + 1][j - 1] and s[i] == s[j] 
1
2
3
4
5
6
7
8
9
10
11
12
13
# This function will recursively check the left and right value of a previous palindromic string
def check(s, bg, ed):
    if bg >= 0 and ed < len(s) and s[bg] == s[ed]:
        return check(s, bg - 1, ed + 1)
    else:
        return s[bg + 1: ed]

for i in range(len(s)):
    # This palindromic substring is with odd num
    longest_palin_string1 = check(s, i, i)

    # This palindromic substring is with even num, we just took the (i, i+1) because the condition of (i-1,i) is already considered in previous steps
    longest_palin_string2 = check(s, i, i + 1)

TBD

No.10 - Two string matching with special character

1
2
3
4
5
if j + 1 == '*':
    p[i][j] = p[i][j+2] or (current_match and p[i+1][j])
else:
    p[i][j] = current_match and p[i+1][j+1]

No.44 - Wildcard Matching

No.322 - Change Coin

1
2
3
4
for coin in coins:
    for j in range(coin, amount+1):
        d[j] = min(d[j], d[j - coin] + 1)
return d[amount]

Package Model

The problem can be described as a decision problem at step i

No.198 - House Robber

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