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

#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;
}

PreviousGreedy Algorithm NextTree

Last updated 3 years ago

Was this helpful?