robturtle
7/11/2017 - 1:38 AM

## Dynamic Programming.md

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.