AI Translated from Chinese
Some BGM
Introduction
Concept
Dynamic programming (DP) is a method used in mathematics, management science, computer science, economics, and bioinformatics to solve complex problems by decomposing the original problem into relatively simpler subproblems.
Dynamic programming is often applicable to problems with overlapping subproblems and optimal substructure properties, and the time it takes is often much less than naive solutions.
Applicable Situations
Optimal substructure property. If the optimal solution of a problem contains the optimal solutions of subproblems, we say the problem has the optimal substructure property (i.e., satisfies the principle of optimality). The optimal substructure property provides important clues for dynamic programming algorithms to solve problems.
No after-effect. Once the solution to a subproblem is determined, it no longer changes, and is not affected by the decisions of larger problems that include it and are solved later.
Subproblem overlap property. The subproblem overlap property refers to the fact that when using a recursive algorithm to solve problems top-down, each subproblem generated is not always a new problem, and some subproblems are calculated multiple times. Dynamic programming algorithms take advantage of this subproblem overlap property, calculating each subproblem only once and storing the results in a table. When needing to calculate a subproblem that has already been calculated, one simply looks up the result in the table, thus achieving higher efficiency and reducing time complexity.
— From Wikipedia - Dynamic Programming
Dynamic programming is not actually a specific algorithm, but a way of thinking and method for solving problems. Simply put, dynamic programming decomposes problems into subproblems and obtains the global optimal solution through the optimal solutions of subproblems (this is called optimal substructure).
Main Text
States and State Transition Equations
The core of dynamic programming is states and state transition equations.
In dynamic programming, states are the results of subproblems, and the current stage’s state is often the result of the previous stage’s state and the previous stage’s decision. The equation describing this inter-stage relationship is the state transition equation.
For example, $ f(i, j) = \max {f(i, k), f(k+1, j)+1} $ is a state transition equation.
Let’s look at some example problems.
Number Triangle
Problem: There is a triangle composed of non-negative integers, with only one number in the first row. Starting from the number in the first row, each time you can go down-left or down-right by one cell until reaching the bottom row. Sum the numbers along the path. How should you walk to maximize the sum?
The number triangle is shown below:
1
/ \
3 2
/ \ / \
4 10 1
/ \ / \ / \
4 3 2 20
Analysis
Greedy Method?
According to the greedy method, the path obtained is: 1 --> 3 --> 10 --> 3
But the actual path with maximum sum is: 1 --> 2 --> 1 --> 20
Clearly, the greedy method cannot guarantee a global optimal solution.
Backtracking?
Each node has two choices. If we use backtracking to find all possible paths, we can find the optimal solution.
However, backtracking is inefficient: a triangle with $ n $ layers has $ 2^{n-1} $ paths, with complexity too high to accept.
As you can see, this is a dynamic decision problem — each time you can choose to go down-left or down-right — which introduces our protagonist today — dynamic programming.
Dynamic Programming
Assume we use a lower triangular matrix (2D array with all elements above the main diagonal as 0) a and d to store the number triangle and the maximum sum starting from d[i][j] respectively.
According to the idea of dynamic programming, to find the maximum sum starting from the first layer (d[1][1], i.e., the maximum sum of paths in the entire number triangle), we must first find the maximum sum starting from the second layer; to find the maximum sum starting from the second layer, we must first find the maximum sum starting from the third layer… By analogy, we can decompose the entire problem into multiple subproblems. Clearly, this problem meets the conditions for dynamic programming:
- Optimal substructure property. By finding the optimal solution of the n-th layer, we can find the optimal solution of the (n-1)-th layer. The optimal solutions of subproblems ultimately guarantee the optimal solution of the entire problem.
- No after-effect. Once the optimal solution of the n-th layer is determined, it is not affected by the previous layers.
- Subproblem overlap property. For example, to calculate
d[2][1], we need to first calculated[3][1]andd[3][2]; and to calculated[2][2], we also need to first calculated[3][2]. This shows that the problem’s solution tree has a lot of overlap, which is exactly where dynamic programming shines.
The state transition equation is as follows:
$ d(i, j) = a(i, j) + \max{d(i+1, j), d(i+1, j+1)} $
Below are two basic dynamic programming approaches.
Method 1: Memoized Search
Direct recursive writing works, but due to subproblem overlap, it leads to a lot of useless repeated calculations. Therefore, we use memoized search to return early.
Core code:
// Since the problem states each number is non-negative integer, initialize d[] to -1, d[i] >= 0 means not calculated
int solve(int i, int j) {
if (d[i][j] >= 0) return d[i][j]; // Already searched, return directly
return d[i][j] = a[i][j] + (i == n ? 0 : max(solve(i+1, j), solve(i+1, j+1))); // Save calculation result and return value
}
This leverages the feature of C language where “assignment statements have return values” to simplify code.
Method 2: Iteration
Note the calculation order; it needs to be computed backwards.
Core code:
void solve() {
for (int i = 1; i <= n; i++) d[n][i] = a[n][i]; // Initialize the last layer
for (int i = n-1; i >= 1; i--) // Iterate backwards
for (int j = 1; j <= i; j++)
d[i][j] = a[i][j] + max(d[i+1][j], d[i+1][j+1]);
cout << d[1][1] << endl;
}
For complete code, refer to the repository (includes a data generator Python script).
Dynamic Programming on DAG
Now we’re connecting with graph theory (￣▽￣)
Related notes: Allen’s Graph Theory Basics
DAG (Directed Acyclic Graph), i.e., a directed graph where you cannot return to the starting point after traversing some edges.
Longest Path with Unfixed Endpoints and Lexicographical Order
Example problem: Nested Rectangles. Problem: Given several rectangles, select as many as possible to arrange in a row, so that except for the last one, each rectangle can be nested (the length and width must be strictly less than the next rectangle; rectangles can be rotated) inside the next rectangle. If there are multiple solutions, the lexicographical order of rectangle numbers should be as small as possible.
As you can see, “nesting” is a binary relationship that can be represented by a graph. We use adjacency matrix to store the graph.
State transition equation: $ d(i) = \max{d(i), d(j)+1} $
Code:
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 100 + 10;
int n;
int G[N][N], a[N], b[N], d[N]; // d[i] represents the longest path length starting from node i
// Read data and build graph
void read_input() {
cin >> n;
int x, y;
for (int i = 1; i <= n; i++) {
cin >> x >> y;
a[i] = min(x, y);
b[i] = max(x, y);
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (a[i] < a[j] && b[i] < b[j]) G[i][j] = 1;
}
// Memoized search, note d[] must be initialized to 0
int dp(int i) {
int &ans = d[i]; // Use reference to simplify reading and writing
if (ans > 0) return ans;
ans = 1;
for (int j = 1; j <= n; j++)
if (G[i][j]) ans = max(ans, dp(j)+1);
return ans;
}
// Recursively print answer, ensuring smallest lexicographical order: try to choose the smallest i and j
void print_ans(int i) {
cout << i << ' ';
for (int j = 1; j <= n; j++) if (G[i][j] && d[i] == d[j]+1) {
print_ans(j);
break; // Exit loop after recursion returns
}
}
int main() {
#ifdef LOCAL
freopen("nested_rectangle.in", "r", stdin);
freopen("nested_rectangle_.out", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
memset(d, 0, sizeof(d));
memset(G, 0, sizeof(G));
read_input();
for (int i = 1; i <= n; i++) dp(i);
int Max = -1, maxi = 1;
for (int i = 1; i <= n; i++)
if (d[i] > Max) { Max = d[i]; maxi = i; }
print_ans(maxi);
cout << "\n\n";
}
return 0;
}
An upgraded version of the example problem, just with an additional dimension, which can completely use the template from the example.
Longest Path and Shortest Path with Fixed Endpoints
Example problem: Coin Problem. There are n types of coins with denominations V1, V2, …, Vn, each with unlimited quantity.
EX: Uva 1347 Tour
The original problem can be transformed into: two people starting from the same point, each moving in turn, finally both reaching the endpoint.
Appendix
References
[1]Wikipedia - Dynamic Programming
[2]Liu Rujia “Algorithm Competition Introduction Basics (2nd Edition)”