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

1. 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

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

3. 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

#include <iostream>
#include <vector>
#include <array>
#include <cmath>
#include <functional>


int main(){
  int row, col;
  std::cin >> row >> col;
  std::vector<std::vector<int>> matrix(row+2);
  for (int i = 0; i <= row+1; ++i){
    std::vector<int> column(col+2);
    matrix[i] = column;
  }
  std::vector<std::vector<int>> ans = matrix;

  for (int i = 1; i <= row; ++i)
    for (int j = 1; j <= col; ++j)
      std::cin >> matrix[i][j];

  // first find all local maximum (greater than four neighbors)
  std::vector<std::array<int, 2>> peak;
  for (int i = 1; i <= row; ++i)
    for (int j = 1; j <= col; ++j)
      if (matrix[i][j] >= matrix[i-1][j] && matrix[i][j] >= matrix[i+1][j] && 
          matrix[i][j] >= matrix[i][j-1] && matrix[i][j] >= matrix[i][j+1])
        peak.push_back({i, j});

  // define recursive lambda function
  const std::vector<std::vector<int>> mat = matrix;
  std::function<int(int, int)> ski = [&mat, &ans, &ski, row, col](int i, int j)->int{
    if (i == 0 || j == 0 || i > row || j > col) return 0;
    if (ans[i][j] != 0) return ans[i][j];
    int best = 1;
    if (mat[i][j] > mat[i-1][j]) best = std::max(best, ski(i-1, j) + 1);
    if (mat[i][j] > mat[i+1][j]) best = std::max(best, ski(i+1, j) + 1);
    if (mat[i][j] > mat[i][j-1]) best = std::max(best, ski(i, j-1) + 1);
    if (mat[i][j] > mat[i][j+1]) best = std::max(best, ski(i, j+1) + 1);
    return ans[i][j] = best;
  };

  // then run DP from each local maximum
  int max_length = 0;
  for (auto p : peak){
    int length = ski(p[0], p[1]);
    if (length > max_length)
      max_length = length;
  }

  std::cout << max_length << std::endl;

  return 0;
}