Dynamic Programming Fundamentals

• Dynamic Programming relies on recursion
• The 3 fundamental parts of Dynamic Programming are:
  • Recursion
  • Memoization
  • Backtracking
• This takes time to understand!

Recursion Fundamentals

• Make the problem smaller in some way
  • What that means depends on the problem!
• Pass the smaller problem to the recursive function
  • Assume output here is correct!
• Use these two tools to construct the solution
• Don't forget the base case!

Memoization Fundamentals

• Don't repeat computations more than once
  • Save previous problem solutions!
• How do you identify the state of a problem?

Backtracking Fundamentals

• Once we have the memo table, we see how the table is filled
• We can take the recursive call out by following the order of the table

0-1 Knapsack Problem

• A backpack can carry weight
• There is set of items to take
• Each item has a weight and benefit value
• Goal: select a subset of the items such that
  • Total weight is at most
  • Maximizing total benefit of the items.

Problem Example

• Solution:

Recursive Solution

• We have 2 inputs we can modify: and
  • We will ignore for now
• A smaller problem is either smaller or smaller
• We can more reliably shrink !

Recursive Solution

• How should we get rid of an element?
  • Make a decision with the element
• Now that we have a smaller problem, what do we do?
  • Make a recursive call!

Recursive Solution

def KnapSack(S, W, n):
# Base Case
if False:
    pass
# Recursive Step
include = KnapSack(S, ?, n - 1) + S[0].b
not_include = KnapSack(S, ?, n - 1)

return None # Not done yet

Recursive Solution

def KnapSack(S, W, n):
# Base Case
if False:
    pass
# Recursive Step
include = KnapSack(S, W - S[n - 1].w, n - 1) + S[0].b
not_include = KnapSack(S, W, n - 1)

return None # Not done yet

Recursive Solution

def KnapSack(S, W, n):
# Base Case
if False:
    pass
# Recursive Step
include = KnapSack(S, W - S[n - 1].w, n - 1) + S[0].b
not_include = KnapSack(S, W, n - 1)

return max(include, not_include)

Recursive Solution

def KnapSack(S, W, n):
# Base Case
if W == 0 or n == 0:
    return 0
if S[0].w > W:
    return KnapSack(S, W, n - 1)
# Recursive Step
include = KnapSack(S, W - S[n - 1].w, n - 1) + S[0].b
not_include = KnapSack(S, W, n - 1)

return max(include, not_include)

Memoization Solution

• Which values are changing in the KnapSack problem?
  • and
• What is a major problem with our current solution?
  • Redoing calculations!
  • Same input = Same output!
• We want to have a table keep track of calculations we already did!

Memoization Solution

• What is the range of in our algorithm?
  • Smallest: 0
  • Largest:
• What is the range of in our algorithm?
  • Smallest: 0
  • Largest:
• A table of size can keep track of every possible answer!

Memoization Solution

memo = Matrix(W, n)
def KnapSack(S, W, n):
# Base Case
if W == 0 or n == 0:
    return 0
if S[0].w > W:
    return KnapSack(S, W, n - 1)
# Recursive Step
include = KnapSack(S, W - S[n - 1].w, n - 1) + S[0].b
not_include = KnapSack(S, W, n - 1)

return max(include, not_include)

Memoization Solution

memo = Matrix(W, n)
def KnapSack(S, W, n):
# Base Case
if W == 0 or n == 0:
    return 0
if memo[W][n] != None:
        return memo[W][n]
if S[0].w > W:
    return KnapSack(S, W, n - 1)
# Recursive Step
include = KnapSack(S, W - S[n - 1].w, n - 1) + S[0].b
not_include = KnapSack(S, W, n - 1)

return max(include, not_include)

Memoization Solution

memo = Matrix(W, n)
def KnapSack(S, W, n):
# Base Case
if W == 0 or n == 0:
    return 0
if memo[W][n] != None:
        return memo[W][n]
if S[0].w > W:
    return memo[W][n] := KnapSack(S, W, n - 1)
# Recursive Step
include = KnapSack(S, W - S[n - 1].w, n - 1) + S[0].b
not_include = KnapSack(S, W, n - 1)

return memo[W][n] := max(include, not_include)

Backtracking Solution

Backtracking Solution

Backtracking Solution

def KnapSack(S, W, N):
    memo = Matrix(W, n)
    for n in range(1, N + 1):
        for w in range(1, W + 1):
            pass

Backtracking Solution

def KnapSack(S, W, N):
    memo = Matrix(W, n)
    for n in range(1, N + 1):
        for w in range(1, W + 1):
            if S[n].w > W:
                memo[w][n] = memo[W][n - 1]
            else:
                include = memo[w - S[n - 1].w][n - 1] + S[n - 1].b
                not_include = memo[w][n - 1]
                memo[w][n] = max(include, not_include)
    return memo[N][W]

Homework Assignment

• There are two homework types: easy and hard
• Points for homework : and
• Doing hard homework requires not doing the previous assignment
• What is the largest number of points you can get?

Problem Example

• Solution:

Recursive Solution

• We have 1 input we can modify:
  • Similar to last time, we are ignoring the set and
• Making the problem smaller means making smaller
• We can shrink with a similar strategy to the Knapsack problem

Recursive Solution

• How do we make this problem smaller?
• How do we then combine the solutions?

Recursive Solution

def Homework(e, h, n): # Not enough parameters!
# Base Case
if False:
    pass
# Recursive Step

return None # Not done yet

Recursive Solution

def Homework(e, h, n, rested):
# Base Case
if n == 0:
    return 0
# Recursive Step
nothing = Homework(e, h, n - 1, True)
easy = e[n - 1] + Homework(e, h, n - 1, False)
hard = h[n - 1] + Homework(e, h, n - 1, False) if rested else 0

return max(nothing, easy, hard) # Not done yet

Backtracking Solution

def Homework(e, h, n):
    memo = Matrix(n, 2)
    for i in range(n):
        for rested in range(2):
            nothing = memo[i - 1][1]
            easy = e[n - 1] + memo[i - 1][0]
            hard = h[n - 1] + memo[n - 1][0] if rested else 0