Dynamic programming problems is problems where it depends on its subproblems multiple times.

General pattern of DP:

solutions = {} # type: Map[subproblem,solution]
def solve(problem):
    recursively solve subproblems of problem

Fibonacci sequence

Ask for S(n): S(n) = S(n-1) + S(n-2)

def fib(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    return fib(n-1) + fib(n-2)

solutions = {0: 0, 1: 1}
def fib(n):
    if n in solutions:
        return solutions[n]
    solution = fib(n-1) + fib(n-2)
    solutions[n] = solution
    return solution

def fib(n):
    a = 1
    b = 0
    if n <= 0:
        return b
    if n == 1:
        return a
    for i in range(2,n+1):
        a, b = a + b, a
    return a

cut robe

prices = [0, 1, 2, 3, 5, 8, 9, 13, 25, 32]

S(n) = max{[S(n-x) + S(x) for x in range(1,n)], prices[n] if n < len(prices)}

def cutrobe(n, prices):
    solutions = [0] * (n+1)
    
    def dp(n):
        if n <= 0:
            return 0
        if solutions[n] > 0:
            return solutions[n]
        m = 0
        if n < len(prices):
            m = prices[n]
        p = max(dp(i) + dp(n-i) for i in range(1,n//2+1))
        m = max(m, p)
        solutions[n] = m
        return m
        
    dp(n)
    return solutions[n]

all pairs shortest path

M is a nxn matrix, where M[i][j] represents distance from i to j. Please compute the matrix S, where S[i][j] is the distance of shortest path from i to j.

M = [
    [0, 3, 2],
    [3, 0, 4],
    [2, 4, 0],
]

S(i,j) => min{S(i,w)+S(w,j) for w in graph}
S(i,w) => min{S(i,t)+S(t,w) for t in graph}

S(i,j,k+1) = min( S(i,j,k), S(i,k+1,k)+S(k+1,j,k) )

knapsack problem

items = [(weight,value)] knapsack of capacity in weight. ask for max value that knapsack can carry.

c = 10
           0        1       2
items = [(3, 5), (4, 6), (2, 2)]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[0, 0, 5, 5, 5, 5, 5, 5, 5, 5]
[0, 0, 5, 6, 6, 6, 11, 11, 11, 11]
[0, 2, 5, 6, 7, 8, 8, 8, 13, 13]

S(k, c) = max( S(k-1,c), S(k-1,c-w[k]) + v[k] )

def knapsack(items, capacity):
    prevs = [0] * (capacity+1)
    maxes = [0] * (capacity+1)
    for weight, value in items:
        for i in range(1, capacity+1):
            maxes[i] = prevs[i]
            if i - weight >= 0:
                maxes[i] = max(prevs[i], prevs[i-weight] + value)
        prevs = list(maxes)
    return maxes[capacity]

DP V.S. Greedy

S(n) => S(n-1) => Safety

activity

Solve: S([0,n)) T(k) is the solution of all activities started after k. Assume, that solution in time range S([0,k)) is already known.

Assume we put the earliest finished activity x, and we don't get the optimum, which meanings:

Exists a solution that exclude x, and the max number is greater.

smallest range

jump game