# Dynamic Programming

Dynamic Programming (DP) problems follow always the same couple of steps. Here they are.

## I. Subproblem definition

DP is about remembering the solution of already computed problems. To remember them, we store them in an array/matrix. Here you define what are your subproblems, ie. how you index your matrix. Here are a couple of example, extracted from other problems:

1. Let $\text{OPT}[i]$ be the maximum profit we can get by building coffee shops in blocks $i$ to $n$.
2. Let $\text{OPT}[k]$ be the maximum value achievable with a capacity of $k$.
3. Let $\text{OPT}[i]$ be the length of the longest increasing subsequence starting at $x[i]$.
4. Let $\text{OPT}[i, j]$ be the edit distance between strings $x[i…n]$ and $y[j…m]$.
5. Let $\text{OPT}[h, i]$ be the maximum grade we can get by spending $h$ hours on assignments from $1$ to $i$.

Once you have given the subproblem definition, tell which one of the subproblems correspond to the original problem. Here are the same examples as before:

1. The final answer is $\text{OPT}[1]$ because we want the maximum profit on blocks from $i=1$ to $n$.

2. The final answer is $\text{OPT}[K]$ because we want the maximum value with capacity $k =K$.

3. The final answer is $\max_{1 \leq j \leq n} \text{OPT}[j]$ because we want the longest increasing subsequence of the string, wherever it starts.

4. The final answer is $\text{OPT}[1, 1]$ because we want the edit distance between strings $x[1…n]$ and $y[1…m]$.

5. The final answer is $\text{OPT}[H, 1]$ because we want the best grade by spending $h = H$ hours on projects from $i = 1$ to $n$.

## II. Recursive formulation

Now that you know what are the subproblems your are going to solve (each cell of the array/matrix OPT is a subproblem), you need to find a recursive formulation between them. Here are the same examples as before:

1. Are we building a coffee ship on block $i$?
• If yes, the maximum profit is $\text{Profit}[i] + \text{OPT}[i+d+1]$,
• if no, it is $\text{OPT}[i+1]$.

But because we don’t know the answer and we want the maximum profit,

$\text{OPT}[i] = \max\big\{ \text{Profit}[i] + \text{OPT}[i+d+1], \text{OPT}[i+1] \big\}$
2. What is the last item added to the knapsack?
• If it is item $i$, the maximum value would be $\text{Value}[i] + \text{OPT}\left[k - \text{Weight}[i]\right]$.

But because we don’t know the answer and we want the maximum value,

$\text{OPT}[k] = \max_{1\leq i \leq n}\big\{\text{Value}[i] + \text{OPT}\left[k - \text{Weight}[i]\right]\big\}$
3. What the next element in the sequence after $a[i]$?
• If it is $a[j]$, the maximum length be $1 + \text{OPT}[j]$.

But because we don’t know the answer and we want the maximum length,

$\text{OPT}[i] = \max_{\substack{i<j\\a[i] \leq a[j]}} \big\{ 1 + \text{OPT}[j] \big\}$
4. What is the optimal alignment for the left-most column?
• if it is $(x[i], -)$, then edit distance would be $1 + \text{OPT}[i+1, j]$,
• if it is $(-, y[j])$, then edit distance would be $1 + \text{OPT}[i, j+1]$,
• if it is $(x[i], y[j])$, then the edit distance would be $I(x[i] = y[j]) + \text{OPT}[i+1, j+1]$.

But because we don’t know the answer and we want the minimum value,

$\text{OPT}[i,j] = \min \big\{ 1 + \text{OPT}[i+1, j], 1 + \text{OPT}[i, j+1], I(x[i] = y[j]) + \text{OPT}[i+1, j+1] \big\}$
5. How many hours are we spending on project $i$?

• If it is $x$, then the maximum grade would be $G_i[x] + \text{OPT}[h-x, i-1]$.

But because we don’t know the answer and we want the maximum value,

$\text{OPT}[h,i] = \max_{1\leq x \leq h} \big\{ G_i[x] + \text{OPT}[h-x, i-1] \big\}$

## III. Algorithm

It is only when you have defined what are your subproblems and given the recursive formulation, that you can think of the algorithm.

// Base cases
...

// Main loop (filling OPT[])
...

// Final result
return ...


## IV. Complexity

Time analysis for DP problems is usually straightforward:

• how many subproblems?

• time per subproblems?