Comment on page

# 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

**States**: optimal substructure**Decisions**: how to pick the best**Boundary**: stop condition**Steps**: the sequence to compute (for bottom-up implementation only)

- 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

- 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

- 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

- 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

- 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

- 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

- Consider all possibilities: list all of them, use optimal substructure
- Take min/max of them
- Save result in DP table

- 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

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

}

Last modified 2yr ago