This article has been machine-translated from Chinese. The translation may contain inaccuracies or awkward phrasing. If in doubt, please refer to the original Chinese version.
Notes from my MOOC study, along with example problem code.
I. General Method for Converting Recursion to Dynamic Programming
If the recursive function has n parameters, define an n-dimensional array where the indices correspond to the range of the recursive function’s parameters. This way, you can fill in the array starting from boundary values, which is essentially the reverse process of computing recursive function values. Example: Problem 1 - Number Triangle.
II. General Approach to Solving DP Problems
1. Decompose the Original Problem into Sub-problems
Decompose the original problem into several sub-problems that have the same or similar form, just at a smaller scale. Once all sub-problems are solved, the original problem is solved. Once a sub-problem’s solution is computed, it is saved, so each sub-problem only needs to be solved once.
2. Define States
State: A set of values for the variables related to sub-problems is called a state. One state corresponds to one or more sub-problems. Value: The value of a state is the solution to the sub-problem(s) corresponding to that state. Time Complexity: The overall time complexity is the number of states multiplied by the time needed per state. Storage: If K integer variables can form a state with value ranges N1, N2, …, Nk respectively, we can use a K-dimensional array array[N1][N2]…[Nk] to store the “value” of each state. This value may not necessarily be a single integer or floating-point number; it could even require a struct, so array can be a struct array.
3. Determine Initial State (Boundary State) Values
4. Determine the State Transition Equation
After defining what a state is and its value, you need to find how different states transition between each other. That is, how to derive one state’s value from one or more states with known values (“everyone helps me” forward-push style). State transitions can be expressed as recurrence formulas, also called “state transition equations.”
III. Characteristics of Problems Solvable by Dynamic Programming
1) Optimal Substructure Property
Optimal substructure property: If the solutions to sub-problems contained in the optimal solution of the problem are also optimal, the problem is said to have this property.
2) No Aftereffect Property
Once the values of several current states are determined, the future evolution of the process depends only on these state values, regardless of the means or path taken to reach these states.
IV. Example Problems
Example 1. Number Triangle
Problem Statement
Given a number triangle consisting of n rows as shown. Design an algorithm to compute a path from the top to the bottom of the triangle such that the sum of numbers along the path is maximized. For a given number triangle of n rows, compute the maximum sum of numbers along a path from top to bottom. The first line of input is the number of rows n, where 1 <= n <= 100. The next n rows contain the numbers in the triangle. All numbers are between 0 and 99. Output a single integer representing the maximum sum.
Sample Input
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
Sample Output
30
Code 1: Memoized Recursive Dynamic Programming
#include <iostream>
#include <algorithm>
#define MAX 101
using namespace std;
//Plain recursion would time out due to too many redundant computations
//So we store each recursive result in an array
//This is called memoized recursive dynamic programming
int D[MAX][MAX];//D[r][j] represents the number at row r, column j (r,j starting from 1)
int maxSum[MAX][MAX];//The best path sum from D(r,j) to the bottom
int n;
int MaxSum(int i, int j) {
if (maxSum[i][j] != -1)
return maxSum[i][j];//If maxSum has been computed before
if (i == n)
maxSum[i][j] = D[i][j];
else {
int x = MaxSum(i+1, j);
int y = MaxSum(i+1, j+1);
maxSum[i][j] = max(x, y) + D[i][j];
}
return maxSum[i][j];
}
int main(){
int i, j;
cin >> n;
for (i = 1; i <= n; i++) {
for (j = 1; j <= i; j++) {
cin >> D[i][j];
maxSum[i][j] = -1;
}
}
cout << MaxSum(1, 1) << endl;
return 0;
}Code 2: Iterative Bottom-Up Dynamic Programming
#include <iostream>
#include <algorithm>
#define MAX 101
using namespace std;
//Iterative bottom-up dynamic programming
int D[MAX][MAX];//D[r][j] represents the number at row r, column j (r,j starting from 1)
int maxSum[MAX][MAX];//The best path sum from D(r,j) to the bottom
int n;
int main(){
int i, j;
cin >> n;
for (i = 1; i <= n; i++) {
for (j = 1; j <= i; j++) {
cin >> D[i][j];
maxSum[i][j] = -1;
}
}
for (i = 1; i <= n; i++)
maxSum[n][i] = D[n][i];
for (i = n-1; i >= 1; i--) {
for (j = 1; j <= i; j++) {
maxSum[i][j] =
max(maxSum[i+1][j], maxSum[i+1][j+1]) + D[i][j];
}
}
cout << maxSum[1][1] << endl;
return 0;
}Example 2. The Magic Pocket
Problem Statement
There is a magical pocket with a total volume of 40. Using this pocket, you can conjure items whose total volume must be exactly 40. John currently has n items he wants, with volumes a1, a2, …, an. John can select some of these items, and if the total volume of the selected items is 40, then the magical pocket can produce them. The question is: how many different ways can John select items?
Input/Output
Input: 3 20 20 20 Output: 3
Code
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int a[30]; int N;
int Ways[40][30];//Ways[i][j] represents the number of ways to achieve volume i from j items
int main() {
cin >> N;
memset(Ways, 0, sizeof(Ways));
for (int i = 1; i <= N; ++i) {
cin >> a[i]; Ways[0][i] = 1;
}
Ways[0][0] = 1;
for (int w = 1; w <= 40; w++) {
for (int k = 1; k <= N; k++) {
Ways[w][k] = Ways[w][k-1];
if (w-a[k] >= 0)
Ways[w][k] += Ways[w-a[k]][k-1];
}
}
cout << Ways[40][N];
return 0;
}Example 3. Longest Common Subsequence
Problem Statement
Given two strings, find the length of their longest common subsequence.
Input/Output Input: abcfbc abfcab programming contest abcd mnp Output: 4 2 0
Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[1001][1001];
/*Approach: Let dp(i,j) represent the length of the LCS of
the first i characters of s1 and the first j characters of s2
dp(n,0) = 0, dp(0,n) = 0;
if (s1[i-1] == s2[j-1]) dp(i,j) = dp(i-1,j-1) + 1;
else dp(i, j) = max(dp(i,j-1), dp(i-1,j));*/
int main() {
string s1, s2;
cin >> s1 >> s2;
int len1 = s1.length();
int len2 = s2.length();
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <=len2; j++) {
if(s1[i-1] == s2[j-1])
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
}
}
cout << dp[len1][len2] << endl;
return 0;
}Example 4. Longest Increasing Subsequence
Problem Statement
The first line of input is the length N of the sequence. The second line contains N integers. Output the length of the longest increasing subsequence.
Input/Output Sample Input: 7 1 7 3 5 9 4 8 Sample Output: 4
Code
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1010;
/*Approach: Decompose into finding the length of the LIS ending at ak.
maxLen(k) represents the length of the LIS ending at ak.
It equals the length of the longest LIS to the left of ak whose last element is smaller than ak, plus 1.
Because any subsequence to the left of ak ending with a value smaller than ak can be extended by appending ak.*/
int a[maxn]; int maxLen[maxn];
int main() {
int N, ans = -1; cin >> N;
for (int i = 1; i <= N; i++) {
cin >> a[i]; maxLen[i] = 1;
}
for (int i = 2; i <= N; i++) {
//Find the length of the LIS ending at the i-th number
for(int j = 1; j < i; j++) {
//The LIS ending at the j-th number
if (a[j] < a[i]) {
maxLen[i] = max(maxLen[i], maxLen[j]+1);
}
}
}
for (int i = 1; i <= N; i++) {
if(maxLen[i] > ans) ans = maxLen[i];
}
cout << ans << endl;
return 0;
}
//Time complexity O(N^2)Adapted from the MOOC “Program Design and Algorithms (2) Dynamic Programming” slides.
喜欢的话，留下你的评论吧～