dynamic programming
Summary
DP fundementals
- state - where you are currently
- means - what we have solved upto this point
- need - what is needed to solve the current state
- decision - decision to make at the current state
- combination - how to compute the current state from previous states
DP patterns
| Pattern | State | Means | Need (sub-problem) | Decision | Combination |
|---|---|---|---|---|---|
| Linear | index i | dp[i] | previous entries | best predecessor | dp[i] = op(dp[i-1], ...) |
| Grid | cell at (r,c) | dp[r][c] | previous sub-grid | direction to arrive from | dp[r][c] = op(dp[r-1][c], dp[r][c-1] |
| Knapsack | index i and remaining capacity | dp[i][rem] | dp[i-1][rem], dp[i-1][rem-weight[i]] | include or exclude i | dp[i][rem] = op(dp[i-1][rem],dp[i-1][ |
| Alignment | indices i and j in two sequences | dp[i][j] | two sequences and sub-sequence excluding i | match | |
| Interval | subrange bounded by (l,r) | dp[l][right] | sub-intervals within the current interval |
otherwise tery tree DP or bitmask DP
Concept
Dynamic programming(DP)
- generic problem solving method
- properties of DP problems:
- overlapping subproblems
- optimal substructure
- avoid repeated calculations, solve sub-problems first
- reduce exponential runtime recursive functions using memoization
Recursion tree
- way of modeling recursive functions
- recursive calls that depend on other recursive calls/the base case(s)
fib(5),
cpp
int fib(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return f(n - 1) + f(n - 2);
}
Recursion DAG
- recursive function + memoization
fib(5)with memoization,
cpp
const int MAXN = 100;
bool found[MAXN];
int memo[MAXN];
int fib(int n) {
if (found[n]) return memo[n];
if (n == 0) return 0;
if (n == 1) return 1;
found[n] = true;
return memo[n] = f(n - 1) + f(n - 2);
}
Bottom-up DP
- start with the basecase
- uses tabulation instead of memoization
- possibly reduce space complexity, but values need to be relaculated every function call
cpp
const int MAX_SAVE = 3; // only the previous, O(1) space
int fib[MAX_SAVE];
int f(int n) {
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i <= n; i++)
fib[i % MAX_SAVE] = fib[(i - 1) % MAX_SAVE] + fib[(i - 2) % MAX_SAVE];
return fib[n % MAX_SAVE];
}
Overlapping subproblems
- when solutions to the same subproblems are needed repeatedly
- store computed solutions to avoid re-computation
- DP cannot help if the subproblems are not overlapping, use divide-and-conquer instead
Optimal substructure
- the most optimal solution of the problem can be built using the opmital solutions of smaller subproblems
- solve small parts optimally, then combine them to get the final optimal answer
- eg. bellman-ford for SSSP
Application
Leetcode: Coin Change
- knapsack
cpp
int dp[amount + 1];
dp[0] = 0;
sort(begin(coins), end(coins)); // sort first
for (int i = 1; i <= amount; i++) {
dp[i] = INT_MAX;
for (int c: coins) {
if (c > i) break; // terminate if coin is larger than the current amount, possible since we sort first
if (dp[i - c] != INT_MAX) dp[i] = min(dp[i], 1 + dp[i - c]); // check if the sub-problem has a solution and use it
// this will result in the minimum coins to reach this current amount
}
}
return dp[amount] == INT_MAX ? -1 : dp[amount];
Codeforces: Vacations
- linear
- tabulate the max number of active days if either resting, contest or sport
cpp
vector<array<int, 3>> dp(n + 1, {0, 0, 0}); // number of active days after i days, if
// on the ith day, rest, contest or sport
for (i = 1; i <= n; i++) {
const auto &prev = dp[i - 1];
// 1st col is max of previous row
dp[i][0] = max(prev[0], max(prev[1], prev[2]));
// 2nd col is max of previous row, or +1 if contest can be done and not consequtive
dp[i][1] = a[i - 1] & 1 ? max(prev[0] + 1, prev[2] + 1) : dp[i][0];
// 3rd col is max of previous row, or +1 if sport can be done and not consequtive
dp[i][2] = a[i - 1] & 2 ? max(prev[0] + 1, prev[1] + 1) : dp[i][0];
}
cout << n - max(dp[n][0], max(dp[n][1], dp[n][2])) << "\n";
return 0;
Leetcode: Longest Common Subsequence
- alignment
cpp
int n = text1.size(), m = text2.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (text1[i - 1] == text2[j - 1]) {
// if same char increment from the diagonal
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
// else choose the longest subsequence from
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[n][m];
- space saving - only two columns