# 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 from $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}$ 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? Quentin Pleplé
June 2013