🌱 Quentin Pleplé

Dynamic Programming

Jun 3rd, 2013

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?

Comments