Here are some notes from my MOOC study, as well as example code.
1. General Transformation Method from Recursion to Dynamic Programming#
If a recursive function has n parameters, define an n-dimensional array, where the indices of the array correspond to the range of values for the parameters of the recursive function.
This way, we can fill the array step by step starting from the boundary values, which is equivalent to calculating the inverse process of the recursive function value. For example, Example 1: Number Triangle.
2. General Approach to Dynamic Programming Problem Solving#
1. Decompose the original problem into subproblems#
Decompose the original problem into several subproblems, which have the same or similar form as the original problem, but with a smaller scale.
Once all subproblems are solved, the original problem is solved.
The solution to each subproblem is saved, so each subproblem only needs to be solved once.
2. Determine the state#
State: Often, a set of values of various variables related to the subproblem is called a state. A state corresponds to one or more subproblems.
Value: The value of a state is the solution to the corresponding subproblem.
Time complexity: The time complexity of the entire problem is the number of states multiplied by the time required for each state.
Storage: If K integer variables can form a state, with value ranges of 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 be an integer or a floating-point number, and may even need to be represented by a structure, so array can be a structure array.
3. Determine the values of some initial states (boundary states)#
4. Determine the state transition equation#
Once the state and its value are defined, we need to find out how to transition from one or more known states to the value of another state ("everyone for me" recursive type). The transition of the state can be expressed by a recursive formula, which can also be called a "state transition equation".
3. Characteristics of Problems Solvable by Dynamic Programming#
1) The problem has the property of optimal substructure#
Optimal substructure: If the solution to the problem contains the optimal solutions to its subproblems, it is said to have this property.
2) No aftereffect#
Once the values of several current states are determined, the subsequent evolution process is only related to the values of these current states, and is not related to the means or paths used before to evolve to these current states.
4. Example Problems#
Example 1: Number Triangle#
Problem Description:
Given a number triangle composed of n rows of numbers as shown in the figure below. Design an algorithm to calculate the maximum sum of the path from the top to the bottom of the triangle.
For the given number triangle composed of n rows of numbers, calculate the maximum sum of the path from the top to the bottom of the triangle.
The first line of the input data is the number of rows n of the number triangle, 1≤n≤100. The next n lines are the numbers in each row of the number triangle. All numbers are between 0 and 99.
The output data is only one integer, representing the calculated maximum value.
Example Input:
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Example Output:
30
Code 1: Memoization Recursive Dynamic Programming Program
#include <iostream>
#include <algorithm>
#define MAX 101
using namespace std;
// If we use recursion, it will exceed the time limit due to too many repeated calculations.
// Therefore, we calculate the result of each recursion and store it in an array.
// This is called memoization recursive dynamic programming program.
int D[MAX][MAX]; // D[r][j] represents the jth number in the rth row (r and j start from 1)
int maxSum[MAX][MAX]; // The sum of the best path from D(r, j) to the bottom edge among all paths
int n;
int MaxSum(int i, int j) {
if (maxSum[i][j] != -1)
return maxSum[i][j]; // If the value of maxSum has been calculated
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: Loop Recurrence Dynamic Programming Program
#include <iostream>
#include <algorithm>
#define MAX 101
using namespace std;
// Loop Recurrence Dynamic Programming Program
int D[MAX][MAX]; // D[r][j] represents the jth number in the rth row (r and j start from 1)
int maxSum[MAX][MAX]; // The sum of the best path from D(r, j) to the bottom edge among all paths
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: Magical Pocket#
Problem Description:
There is a magical pocket with a total capacity of 40. Using this pocket, you can produce some items, and the total volume of these items must be 40. John now has n items that he wants to obtain, and the volume of each item is a1, a2, ..., an. John can choose some items from these items. If the total volume of the selected items is 40, John can obtain these items using the magical pocket. The problem now is how many different ways John can choose the items.
Input and 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 make a volume of i using j kinds of 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 Description:
Given two strings, find the length of the longest common subsequence.
Input and 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];
/* Idea: Let dp(i, j) represent the length of the longest common subsequence of the substring formed by 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 Description:
The first line of input is the length N of the sequence, and the second line is N integers.
Output the length of the longest increasing subsequence.
Input and Output:
Input Example:
7
1 7 3 5 9 4 8
Output Example:
4
Code:
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1010;
/* Idea: Decompose it into finding the length of the longest increasing subsequence with ak as the endpoint.
maxLen(k) represents the length of the longest increasing subsequence with ak as the endpoint.
It is the length of the longest increasing subsequence with a value smaller than ak on the left plus 1.
Because any subsequence on the left of ak with a smaller endpoint than ak can form a longer increasing subsequence by adding 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++) {
// Calculate the length of the longest increasing subsequence with the ith number as the endpoint
for(int j = 1; j < i; j++) {
// The longest increasing subsequence with the jth number as the endpoint
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)