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: itemcan be usedtimes
- makecopies of item
- add one more dimensionwith constraint(the state will be)
- 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