Dynamic Programming (DP)
Page content
 A technique for efficiently implementing a recursive algorithm by storing partial results
 It starts with a recursive algorithm or definition.
 How to solve a DP problem
 The problem can be broken down into “overlapping subproblems”smaller versions of the original problem that are reused multiple times.
 The problem has an “optimal substructure”an optimal solution can be formed from optimal solutions to the overlapping subproblems of the original problem.
Implementing a DP algorithm
1. Bottomup (Tabulation)
 It is implemented with iteration and starts at the base cases.
 It is implemented with nested loops and an array.
F = array of length (n + 1)
F[0] = 0
F[1] = 1
for i from 2 to n:
F[i] = F[i  1] + F[i  2]
2. Topdown (Memoization)
 It is implemented with recursion and made efficient with memoization.
 It is implemented with a recursive function and hash map.
 Memoizing a result means storing the result of a function call, usually in a hashmap or an array, so that when the same function call is made again, we can simply return the memoized result instead of recalculating the result.
memo = hashmap
Function F(integer i):
if i is 0 or 1:
return i
if i doesn't exist in memo:
memo[i] = F(i  1) + F(i  2)
return memo[i]
Bottomup vs. topdown
 Bottomup
 usually smaller space complexity and faster runtime, as iteration does not have the overhead that recursion does.
 We need to go through a logical ordering of solving subproblems.
 Topdown
 easy to write
 Ordering of subproblems does not matter with recursion.
How to convert the topdown solution to the bottomup
 Initialize an array
dp
that is sized according to your state variables. For example, 2Darray fornums
andk
.  If it asks for the max (min) of sth, set the values $\infty$ ($\infty$).
 Set your base cases, the same as the topdown function.
 Write a for loop that iterates over the state variables. If you have multiple states, you will need to be nested for loops. These loops should start iterating from the base cases.
 Each iteration of the innermost loop represents a given state and is equivalent to a function call to the same state in topdown.
 Return the answer to the original problem.
How to solve a DP problem
(1) A function or data structure that will compute/contain the answer to the problem for every given state.

When designing the function/array, we need to decide on state variables to pass as arguments.

Common state variables:
 An index along some input, $i$.
 A second index along some input, $j$.
 Explicit numerical constraints are given in the problem, $k$.
 Variables that describe statuses in a given state. i.e. “true if currently holding a key, false if not”, “currently holding $k$ packages” etc.
 Some sort of data like a tuple or bitmask used to indicate things being “visited” or “used”. “bitmask is a mask where the $i_{th}$ bit indicates if the $i_{th}$ city has been visited”.

i.e. House Robber Problem
 The only state variable is an integer $i$, which indicates the index of a house.
 If the problem had an added constraint such as “you are only allowed to rob up to $k$ houses”, then $k$ would be another necessary state variable.
(2) A recurrence relation to transition between states.
 A recurrence relation is an equation that relates different states with each other.
 It is closer to our natural way of thinking.
 Start to think about a general state ($i_{th}$) and use information from the problem description to think about how other states relate to the current one.
(3) Base cases, so that our recurrence relation doesn’t go on infinitely.
Time and space complexity
 Time complexity is directly tied to the number of possible states.
 If computing each state requires $F$ time, and there are $n$ possible states, then the time complexity of a DP algorithm is $O(nF)$.
 Computing a state has just been using a recurrence relation equation, which is $O(1)$. Therefore, the time complexity has just been equal to the number of states. To find the number of states, look at each of your state variables, compute the number of values each one can represent, and then multiply all these numbers together.
Ordered partition
Approximate string match
Longest common substring
def longestCommonSubstring(text1: str, text2: str) > int:
m, n = len(text1), len(text2)
dp_matrix = [ [0] * (n+1) for _ in range(m+1) ]
max_len = 0
for col in range(1, n+1):
for row in range(1, m+1):
if text1[row1] == text2[col1]:
dp_matrix[row][col] = dp_matrix[row1][col1]+1
max_len = max(max_len, dp_matrix[row][col])
else:
dp_matrix[row][col] = max(dp_matrix[row1][col], dp_matrix[row][col1])
return max_len
print(longestCommonSubstring("money", "monkey"))
Edit distance
def edit_distance(word1, word2):
m = len(word1)
n = len(word2)
edit_distance_matrix = [ [0] * (n + 1) for i in range(m + 1) ]
for row in range(m + 1):
for column in range(n + 1):
if row == 0:
edit_distance_matrix[row][column] = column
elif column == 0:
edit_distance_matrix[row][column] = row
elif word1[row  1] == word2[column  1]:
edit_distance_matrix[row][column] = edit_distance_matrix[row  1][column  1]
else:
edit_distance_matrix[row][column] = 1 + min(edit_distance_matrix[row][column  1],
edit_distance_matrix[row  1][column],
edit_distance_matrix[row  1][column  1])
return edit_distance_matrix[m][n]
print(edit_distance("MONKEY", "MONEY"))
Brute force
 Time Complexity: $O(3^n)$ (In the worst case, we have three choices for every step.)
int editDistance(String word1, String word2) {
if (word1 == null  word1.length() == 0)
return word2.length()
if (word2 == null  word2.length() == 0)
return word1.length()
return match(word1, word2, 0, 0)
}
int match(String s1, String s2, int i, int j) {
//If one of the string's pointer has reached the end of it
if (s1.length() == i)
return s2.length()  j
if (s2.length() == j)
return s1.length()  i
int result
// If current position is the same.
if (s1[i] == s2[j]) {
result = match(s1, s2, i + 1, j + 1)
} else {
//Case1: insert
int insert = match(s1, s2, i, j + 1)
//Case2: delete
int delete = match(s1, s2, i + 1, j)
//Case3: substitute
int substitute = match(s1, s2, i + 1, j + 1)
result = min(insert, delete, substitute) + 1
}
return result
}
row_init(int i) {
m[0][i].cost = i;
if (i>0)
m[0][i].parent = INSERT;
else
m[0][i].parent = 1;
}
Special cases of edit distance
Substring matching
 Find where a short pattern
P
best occurs within a long textT
 Search for “Skiena” in all its misspellings (Skienna, Skena, Skina, . . . ) within a long file.
void row_init(int i, cell m[MAXLEN+1][MAXLEN+1]) {
m[0][i].cost = 0;
m[0][i].parent = 1;
}
Longest common subsequence
 Find the longest scattered string of characters included within both strings, without changing their relative order.
 i.e.
LCS(“democrats", "republicans") = "ecas"
 i.e.
int match(char c, char d) {
if (c == d) {
return(0);
}
return(MAXLEN);
}
Maximum monotone subsequence
 Seek to delete the fewest number of elements from an input string
S
to leave a monotonically increasing subsequence i.e.
MMS(243517698) = 23568
 i.e.
Longest increasing subsequence
from typing import List
def len_of_lis(nums: List[int]) > int:
dp = [1] * len(nums)
for i in range(1, len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
nums = [10,9,2,5,3,7,101,18]
print(len_of_lis(nums))
Parsing contextfree grammar
Subset sum
def isSubsetSum(arr, n, sum, dp):
if sum_ == 0:
return True
if n == 0 and sum_ != 0:
return False
if dp[n][sum_] != 1:
return dp[n][sum_]
if arr[n  1] > sum_:
return isSubsetSum(arr, n  1, sum_, dp)
dp[n][sum_] = isSubsetSum(arr, n  1, sum_, dp) or isSubsetSum(arr, n  1, sum_  arr[n  1], dp)
return dp[n][sum_]
def findPartition(arr, n):
sum_ = 0
for i in range(n):
sum_ += arr[i]
if sum_ % 2 != 0:
return False
dp = [[1]*(sum_+1)]*(n+1)
return isSubsetSum(arr, n, sum_ // 2, dp)
arr = [ 3, 1, 5, 9, 12 ]
n = len(arr)
if findPartition(arr, n):
print("Can be divided into two subsets of equal sum")
else:
print("Can not be divided into two subsets of equal sum")
arr2 = [ 3, 1, 5, 9, 14 ]
n2 = len(arr2)
if findPartition(arr2, n2):
print("Can be divided into two subsets of equal sum")
else:
print("Can not be divided into two subsets of equal sum")