I accidentally reviewed the review with my colleagues two days ago and found that the algorithms in the previous functional business were really unsightly. The entire algorithm structure exceeds 50 lines…all if, else. The main focus is a customized explanation of a special problem, but this also exposed multiple problems.
In fact, in many development tasks, when it comes to functional modules, because each person’s work experience is different, the number of business scenarios that the written modules can carry is different. But there is no doubt that the idea of dynamic programming can make the written functional modules more stable and elegant to a certain extent~
So in response to this situation, today I specially wrote an article about dynamic programming for myself.
1. Simple summary
Dynamic rules, in short, are a method of splitting small problems into big problems, getting the current optimal solution to small problems with greedy thinking, storing the results, and then sharing them with other problems. Compare small problems until you get the optimal solution to the entire small problem and then exit.
How to understand this sentence? For example, at the same moment, Xiao Li’s wife asked him to send his children to school, but his boss called and asked Xiao Li to immediately fix a bug that affected the project’s launch. Then at this time, the hot water kettle on the floor was tipped over by the child and burned Xiao Li’s feet. 0.o
Okay, let’s dynamically plan the entire scenario. If you were Xiao Li, how would you handle this scenario?
Of course, this example is not appropriate. After all, everyone views everything differently. However, this example is just an abstract example and does not need to be too realistic~
Let’s analyze it. The overall problem is to deal with the current things that affect your original plan. The problem here is ① sending the child, problem ② fixing the bug, and problem ③ being burned by hot water.
If split into the problem structure, it is, ①, ①②, ①②③.
Judging from the current mainstream social values, if there is only one problem ①, then just send the child away. If the problem is ①②, then Xiao Li must have fixed the bug and handed the child to his wife to deliver. If the problem is ①②③, then don’t say anything, rinse your feet with cold water first, then fix the bug, and leave the child to his wife to deliver.
What this example actually means is that when the entire problem appears in front of you, try to analyze how to deal with this situation in the local problem, and finally get the optimal solution based on the current problem.
2. Concrete examples
Here we take two questions as examples. Let’s start with a simple question Niuke.com
Question link: Climb the stairs at the minimum cost_Niuke Topic_Niuke.com
Question requirements: Given an integer array cost, where cost[i] is the cost to climb up the i\ith step of the staircase, and the subscript starts from 0. Once you pay this fee, you have the option of climbing up one or two steps. You can choose to start climbing the stairs from the step with index 0 or index 1. Please calculate and return the minimum cost to reach the top of the stairs.
In short, it gives you an array. You can start crawling from 0 and 1 in the table below. You can crawl one or two at a time, but no matter whether you crawl one or two, you need to pay for the current elements in the table below. price. It does not end until the number of array elements is jumped out.
It is not difficult to analyze this question. First of all, the sub-problem of each step is that my step can be obtained by the previous step + 1, or it can be obtained by the previous step + 1. So how do I know which one I want to choose?
It’s very simple. Let’s see if it is obtained by the previous step + 1. We can look at the cost of (the previous step)’s arrival plus (the previous step )belongs to(the array subscript money)contrast(go up the previous step)the cost of reaching the destination plus(go up the previous step and belongs to the array below bid money). Whichever one is smaller, we will choose.
Implementation:
int minCostClimbingStairs(vector<int> & amp; cost) {
vector<int> dp(cost.size() + 1,0);//Storage the results of each level of steps
for(int i = 2;i<=cost.size();i + + ) {
dp[i] = min(cost[i-1] + dp[i-1],cost[i-2] + dp[i-2]);
}//Loop through to obtain the optimal result of each step starting from the second step.
return *(dp.end()-1);
}
A big boss has said it here. The example you gave is so simple, it’s deceiving people, isn’t it?
Okay, okay, since the boss said so, let’s make it a little more difficult.
Such as the title: Longest common subsequence (2)_Niuke question breaker_Niuke.com
Question requirement: Given two strings str1 and str2, output the longest common subsequence of the two strings. If the longest common subsequence is empty, return “-1”. In the data currently given, there will only be one longest common subsequence. Data range: 0 \le |str1|,|str2| \le 20000≤∣str1∣,∣str2∣≤2000. Space complexity O(n^2)O(n2), time complexity O(n^2)O(n2)
In short, given two strings, it is required to find the longest subsequence that is the same inside. (Subsequence is different from string, it can be obtained across characters)
Analyze it: Here, assume there are str1 and str2. Then what we have to do is divide the two strings in the form of two-dimensional arrays, and store the coordinates of the same number of subsequences into the two-dimensional array we created.
What does it mean? As shown below:
Some students will ask, why is there a blank row and why the column is not moved one space to the left?
That’s because we need to use dp[i][j] to store the position of the same character, so we must ensure that the initial value dp[0][0] = 0, so the size of the opened space should also be Str1.size() + 1 and Str2.size() + 1
Specific code:
class Solution {
public:
string OneStr = "";
string TwoStr = "";
string GetStringResult(size_t i,size_t j,vector<vector<int>> & tempNum)
{
string res = "";
if (i==0 || j==0) {
return res;
}
if (tempNum[i][j]== 1) {
res + = GetStringResult(i-1, j-1,tempNum);//Same as passing in the previous character position and continue traversing
res + = TwoStr[j-1];//You can also write res + = OneStr[i-1] here. The effect is the same, because the character position at each level stores the previous character element, so res is superimposed When, you need to get the character element content
}
else if(tempNum[i][j]==2) { res + = GetStringResult(i - 1, j, tempNum);//Because it comes from the left, I have to continue running to the left until I find the sign of the same character Bit}
else if(tempNum[i][j] == 3) { res + = GetStringResult(i,j - 1, tempNum);}
return res;
}
string LCS(string s1, string s2) {
OneStr = s1;
TwoStr = s2;
if (s1.length() == 0 || s2.length() ==0) {
return "-1";
}
vector<vector<int>> dp(s1.size() + 1,vector<int>(s2.size() + 1,0));//Storage the same length
vector<vector<int>> tempNum(s1.size() + 1,vector<int>(s2.size() + 1,0));//Storage flag bit
for (int i = 1; i<=s1.size();i + + ) {
for (int j = 1;j<=s2.size();j + + ) {
if(s1[i-1] == s2[j-1]) {//Indicates the same characters, temporary storage location
dp[i][j] = dp[i-1][j-1] + 1;//Based on the same length of the previous character + 1
tempNum[i][j] = 1;//Set flag at this level
}
else {
if(dp[i-1][j] > dp[i][j-1]) { //Not the same, coming from the left
dp[i][j] = dp[i-1][j];//Continue the character length on the left
tempNum[i][j] = 2;//Set flag at this level
} else {
dp[i][j] = dp[i][j-1];//Continue the character length above
tempNum[i][j] = 3;//Set flag at this level
}
}
}
}
string res = GetStringResult(s1.size(),s2.size(),tempNum);
return res != "" ? res : "-1";
}
};
In summary, we use abstraction and concreteness to explain the ideas about dynamic programming. If you find anything unreasonable, please feel free to discuss it with the blogger.