Dynamic programming algorithms are optimized from brute force search algorithms. If we do not understand the process of brute force search, it will be difficult to understand the implementation of dynamic programming. When we understand the text overview of the basic principles of dynamic programming algorithms and implement the conditions, we may not understand this idea very much, and we have no idea to start when facing practical problems. At this time, we cannot stay at the text level, but should learn the implementation of classic dynamic programming algorithms, and then look back at these concepts, and then we will suddenly realize it.
The difficulty of dynamic programming algorithms lies in abstracting the dynamic programming table dp from practical problems. dp is generally an array, which may be one-dimensional, two-dimensional, or other data structures.
Key points of dynamic programming:
1. Optimization principle, that is, the most substructure property. This refers to the nature of an optimization strategy. Regardless of the past state and decision-making, for the state formed by the previous decision, the remaining decisions must constitute the optimal strategy. Simply put, the sub-strategy of an optimization strategy is always optimal. If a problem meets the optimization principle, it is said to have the optimal sub-structure properties.
2. No aftereffect refers to the benefits of decision making in a certain state, which is only related to the state and decision making, and has nothing to do with the way to achieve that state.
3. Overlapping of subproblems. Dynamic programming improves the original exponential brute-force search algorithm to an algorithm with polynomial time complexity. The key is to solve the problem of honor and repeated calculations. This is the fundamental purpose of dynamic programming algorithms.
4. Generally speaking, dynamic programming algorithms are a series of algorithms that exchange space for time.
Case 1:
There are n-level steps. Every time a person goes up one or two levels, asks how many ways to complete n-level steps.
Analysis: The key to realizing dynamic programming lies in whether the dynamic programming table can be used accurately and reasonably to abstract practical problems. On this issue, we let f(n) represent the number of methods to go up to n levels.
Then when n is 1, f(n) = 1, n is 2, f(n) = 2, that is, when there are only one step, the number of methods is one, and when there are two steps, the number of methods is 2. Then when we want to go up to n-level steps, we must take one step from n-1 or two steps from n-2 steps. Therefore, the number of methods to reach n-level steps must be the sum of the number of methods to reach n-1 steps plus the number of methods to reach n-2 steps. That is, f(n) = f(n-1)+f(n-2), we use dp[n] to represent the dynamic programming table, dp[i], i>0, i<=n, and the number of methods to reach the i-level step.
/*dp is a global array, size n, all initialized to 0, it is the dynamic programming table in the question*/
int fun(int n){
if (n==1||n==2)
return n;
/*Judge whether the state of n-1 has been calculated*/
if (!dp[n-1])
dp[n-1] = fun(n-1);
if(!dp[n-2])
dp[n-2]=fun(n-2);
return dp[n-1]+dp[n-2];
}Case 2:
Given a matrix m, starting from the upper left corner, you can only walk right or down each time, and finally reach the position in the lower right corner, all numbers in the path are accumulated as the path sum, returning the minimum path sum of all paths. If the given m is as follows, then paths 1, 3, 1, 0, 6, 1, 0 are the minimum path sum, returning 12.
1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0
Analysis: For this question, assuming m is a matrix of m rows and n columns, then we use dp[m][n] to abstract this problem. dp[i][j] represents the sum of the shortest paths from the origin to the positions i and j. We first calculate the first row and the first column, and just accumulate it directly. For other positions, we either reach it from the left position or from the upper position. We take the smaller value on the left and upper, and then add the current path value to the shortest path to reach the current point. Then calculate from left to right, from top to bottom.
#include <iostream>
#include <algorithm>
using namespace std;
int dp[4][4] = {};
int main(){
int arr[4][4] = {1,3,5,9,8,1,3,4,5,0,6,1,8,8,4,0};
//cout << fun(arr,4,4) << endl;
const int oo = ~0U>>2;
for (int i = 0;i<4;i++)
for (int j = 0; j < 4;j++)
dp[i][j] = oo;
//dp[0][0] = oo;
for (int i = 0; i < 4;i++){
for (int j = 0; j<4;j++){
if (dp[i][j] == oo){
if (i==0&&j==0)
dp[i][j] = arr[i][j];
else if (i==0&&j!=0)
dp[i][j] = arr[i][j] + dp[i][j-1];
else if(i!=0&&j==0)
dp[i][j] = arr[i][j] + dp[i-1][j];
else{
dp[i][j] = arr[i][j]+min(dp[i-1][j],dp[i][j-1]);
}
}
}
}
// cout << dp[3][3] << endl;
for (int i = 0; i< 4;i++){
for (int j = 0; j<4;j++){
cout << dp[i][j] << " ";
}
cout << endl;
}
}Given an array arr, return the length of the longest incremental subsequence of arr, such as arr=[2,1,5,3,6,4,8,9,7], and the longest incremental subsequence is [1,3,4,8,9] and returns its length as 5.
analyze:
First, an array of dp[n] is generated, which represents the length of the maximum incremental subsequence generated when the number arr[i] must end. For the first number, it is obvious that dp[0] is 1. When we calculate dp[i], we examine all positions before position i, find the largest dp value before position i, and record it as dp[j](0=<j<i), dp[j] represents the longest incremental sequence ending with arr[j], and dp[j] is the largest value calculated before. We will judge whether arr[i] is greater than arr[j], if it is greater than dp[i]=dp[j]+1. After calculating dp, we find the maximum value in dp, that is, the longest incremental sequence of this string.
#include <iostream>
#include <algorithm>
using namespace std;
/*Dynamic Programming Table*/
int dp[5] = {};
int main(){
int arr[5] = {2,4,5,3,1};
dp[0] = 1;
const int oo = 0;
for (int i = 1;i<5;i++){
int _max = oo;
for (int j=0;j<i;j++)
if(dp[j]>_max&&arr[i]>arr[j])
_max = dp[j];
dp[i] = _max+1;
}
int maxlist=0;
for (int i = 0; i < 5;i++)
if (dp[i] > maxlist)
maxlist=dp[i];
cout << maxlist << endl;
}Case 4:
Given the two strings str1 and str2, return the longest common subsequence of the two strings, for example: str1="1A2C3D4B56", str2="B1D23CA45B6A", "123456" and "12C4B6" are both the longest common subsequences, and return either one is OK.
Analysis: This question is a very classic dynamic programming problem. Assuming that the length of str1 is M and the length of str2 is N, a two-dimensional array dp of M*N is generated. The meaning of dp[i][j] is the length of the longest common subsequence of str1[0..i] and str2[0..j].
The method for finding the dp value is as follows:
The value of dp[i][j] must be related to dp[i-1][j], dp[i][j-1], dp[i-1][j-1]. Combined with the following code, we actually started to calculate from row 1 and column 1, and initialized both row 0 and column 0 to 0. This is to facilitate the subsequent maximum value in code implementation. dp[i][j] takes the maximum value between the three.
int findLCS(string A, int n, string B, int m) {
// n represents the length of string A, m represents the length of string B
int dp[500][500] = {};
for (int i = 0;i < n;i++)
{
for (int j = 0; j<m;j++)
{
if (A[i]==B[j])
dp[i+1][j+1] = dp[i][j]+1;
else
dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1]);
}
}
return dp[n][m];
}Case 5:
Backpack problem, a classic problem of dynamic planning. A backpack has a titrated load-bearing W, and there are N items. Each item has its own value. It is recorded in array V and has its own weight. It is recorded in array W. It can only be selected whether to load or not to load each item. It is required that the total value of the selected items is the largest if it does not exceed the load-bearing of the backpack.
Analysis: Assuming the item number is from 1 to n, consider whether to add the backpack one by one, assuming that dp[x][y] represents the maximum value of the previous x item, and does not exceed the weight y, enumerate the situation of the x item:
Case 1: If the xth item is selected, the weight obtained by the first x-1 item cannot exceed y-w[x].
Case 2: If the xth item is not selected, the weight obtained by the first x-1 item does not exceed y.
Therefore, dp[x][y] may be equal to dp[x-1][y], that is, when the xth item is not taken, the value is the same as before, or it may be dp[x-1][y-w[x]]+v[x], that is, when the xth item is taken, of course, you will get the value of the xth item. Among the two possible options, the one with greater value should be chosen, that is:
dp[x][y] = max{dp[x-1][y],dp[x-1][y-w[x]]+v[x]}
Therefore, for the dp matrix, the number of rows is the number of items n and the number of columns is the weight w of the backpack. From left to right, from top to bottom, the dp value can be calculated in turn.
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
/*Item quantity*/
int n = 4;
/*Backpack load bearing*/
int cap = 10;
int v[4] = {42,12,40,25};
int w[4] = {7,3,4,5};
/*Two-dimensional dynamic programming table*/
vector<int> p(cap+1,0);
vector<vector<int>> dp(n+1,p);
for (int i = 1;i <=n;i++){/*Enum items*/
for (int j = 1;j<cap+1;j++){/*Enum weight*/
/*Judge the relationship between the weight of the enumeration and the weight of the currently selected item
If the sum of enumeration is greater than or equal to the selected item, you need to determine whether the current item is selected*/
if (j-w[i-1]>=0)
dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1]);
else
/*If the enumeration weight is not as heavy as the currently selected item, then it can only be to not take the current item*/
dp[i][j] = dp[i-1][j];
}
}
cout << dp[n][cap] << endl;
}Case 6:
Given two strings str1 and str2, given three integers ic, dc, rc, respectively, represent the cost of inserting, deleting and replacing a character. Return to str1
The price of editing to str2, for example, str1="abc",str2="adc",ic=5,dc=3,rc=2, from str1 to str2, the cost of changing 'b' to 'd' is the smallest, so return 2.
analyze:
When building a dynamic planning table, the key is to figure out the source of the values at each position. First, we generate a dynamic programming table of dp[M+1][N+1]. M represents the length of str1 and N represents the length of str2. Then dp[i][j] is the minimum cost of str1[0..i-1] becoming str2[0...j-1]. Then the sources of dp[i][j] come from the following four situations:
a. First delete str1[i-1] and turn it into str1[0...i-2], and then turn str1[0...i-2] into str2[0...j-1], then dp[i-1][j] represents the minimum cost from str1[0..i-2] to str2[0...j-1], so: dp[i][j] = dp[i-1][j]+dc;
b. Similarly, it can also change from str1[0...i-1] to str2[0...j-2], and then insert str2[j-1], dp[i][j-1] means the smallest person from str1[0...i-1] to str2[0...j-2], so: dp[i][j] = dp[i][j-1]+ic;
c. If str[i-1] == str2[j-1], you only need to turn str1[0...i-2] into str2[0...j-2], at this time dp[i][j] = dp[i-1][j-1];
d. If str1[i-1]!=str2[j-1], we only need to replace str1[i-1] with str2[j-1], at this time dp[i][j] = dp[i-1][j-1]+rc;
Among these four situations, we choose the smallest one, which is the minimum price.
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
string str1 = "ab12cd3";
string str2 = "abcdf";
//cin>>str1;
//cin>>str2;
const int M = ();
const int N = ();
//vector<int> p(M+1,0);
//vector<vector<int>> dp(N+1,p);
int dp[10][10] = {};
int ic=5,dc=3,rc=2;
//int ic = 1,dc=1,rc=1;
dp[0][0] = 0;
for (int i = 1;i<N+1;i++)
dp[0][i] = ic*i;
for (int i = 1;i<M+1;i++)
dp[i][0] = dc*i;
for (int i=0;i<M;i++){
for (int j = 0;j<N;j++){
int x = min(dc+dp[i+1][j],dp[i][j+1]+ic);
if (str1[i]!=str2[j])
dp[i+1][j+1] = min(dp[i][j] + rc,x);
else
dp[i+1][j+1] = min(dp[i][j],x);
}
}
cout << dp[M][N] << endl;
}