# Dynamic Programming

also applied to optimization problems

make the best decision based on history

common solution to more complicated DP problems: add more dimensions!

the challenging part is to find the "correct" state to solve recursively

common mistake: something wrong at stop condition

### Three (and a half) components

**States**: optimal substructure**Decisions**: how to pick the best**Boundary**: stop condition**Steps**: the sequence to compute (for bottom-up implementation only)

### Example Problems

Knapsack problem and its variants

Longest Common Subsequence (LCS)

Edit distance

Single-source Shortest Path (SSSP) on DAGs

Matrix multiplication chain

DP on trees (no-boss party)

DP for games (NIM, Tic-Tac-Toe, Go)

Longest Increasing Subsequence (LIC)

Variant of Activity Selection (longest total length, largest total value, limited size)

Line-breaking problem in Latex

#### Knapsack Problems

unbounded knapsack

0/1 knapsack

Multiple knapsack problem: item$j$can be used$x_j$times

make $x_j$copies of item$j$

add one more dimension$k$with constraint$k \le x_j$(the state will be$S_{ijk}$)

Some of them cannot be added together

for arbitrary constraint, it can be NP-hard

for 2-item case, if we can pick only one of (a1, a2), we can consider the pair as j

manually write down three possible states [a1, a2, none] in the recurrence

Each item has more than one dimension (e.g., both weight and volume)

just add one more dimension for volume

Dependencies between items (HW Problem C?)

depends on the structure (tree, DAG, etc.), we can still run DP on it

probably need to use memorization as well

### Implementation

Top-down method: solve recursively

easy to implement

straightforward when the recurrence relation has been established

compute upon needed

fast if don't go too deep in the recursion tree

will consume too much memory on stack and become slow

Bottom-up method: non-recursive

hard to implement (need to be extremely careful about prerequisites)

data must be ready before get used; can easily make mistakes here

will add the fourth component to DP problem:

**steps**(the sequence to compute)

run on each level sequentially

fast if all computed states are useful/needed

in some cases, computed states are not used later on, which is a waste of time

### Design a DP algorithm

find optimal substructure and represent the subproblems as states

find the critical properties related to subproblems

if it doesn't work, consider add one more dimension to the state

write down the recurrence between the states, and carefully check the boundary cases

write down the DP algorithm according to the recurrence

recursive or non-recursive implementation

memorization

### Summary

#### State: what is the index of your DP table?

It can describe the current stage

Knapsack: f[i, j]: first i items with weight j

LCS/Edit distance: f[i, j]: first i characters in X and first j characters in Y

LIS: f[i]: LIS of the first i elements

Activity selection: f[i]: first i activities

It can be the amount of “resource” used

Knapsack: f[i, j]: first i items with weight j

Activity selection: f[i, j]: first i activities up to time j

Tree DP: f[i, j]: i’th subtree with j elements selected

It can be the current “situation”

DP for games: f[i]: i describes the current “chessboard”

It can be an interval

Matrix multiplication chain: f[i, j]: best result of processing the i-th element to the j-th element

#### Boundary: stop condition; no dependence on any other states

f[0], f[0, 0]

f[0, j], f[i, 0]

f[i, i]

f[s] for a certain s (starting point)

f[i] = xxx if i = yyy

#### Decision: compute the current state based on previous states

Consider all possibilities: list all of them, use optimal substructure

Take min/max of them

Save result in DP table

#### Tricks

When you have more constrains, add a dimension

Knapsack f[i, j, k, l, ..]: first i items with weight j, volume k, price l …

By using different variables in the state, we can get different algorithms

Activity selection: using f[i] as “best result using first i activities with i selected”. O(n^2) time

Activity selection: using f[i, j] as “best result using first i activities up to time j”. O(nt) time

When the ordering is hard to decide, consider using memorization

## Example Code: Ski - 2D LIS

Last updated