This is the first day of my participation in the Gwen Challenge in November. Check out the details: the last Gwen Challenge in 2021
preface
Hello everyone, I am Bigsai, long time no see, very miss (miss every day)!
A long time ago, some friends were tortured by dynamic programming. Indeed, many dynamic programming problems were really difficult to see, and some problems even took a long time to understand.
Although the scope of dynamic programming is indeed very wide and difficult, from the frequency of the whole dynamic programming, these basic dynamic programming is easy to understand, not much pressure to learn, and the frequency of occurrence is very high.
These common dynamic programming are: maximum sum of continuous subarrays, maximum product of subarrays, longest increasing subsequence (LIS), longest common subsequence (LCS), longest common subsequence, longest common subsequence, different subsequence.
The first public account bigsai, declined to reprint without contact
What is dynamic programming
First of all, a lot of people ask, what is dynamic programming? Dynamic Programming (DP) is a branch of operations research. It is a process to solve the optimization of decision process. Popular dynamic programming is a top-down (front-to-back) stepwise approach to solving numbers.
So what’s the difference and connection between dynamic programming and recursion?
In general, dynamic planning has different strategies from front to back and recursion from back to front. In general, dynamic planning is more efficient than recursion.
But you have to think about the initial state, the relationship between the upper and lower levels of data. A lot of times problems that you can solve with dynamic programming, you can solve with recursion but a lot of times it’s not very efficient and you might want to use mnemonic search.
Not sure?
Take Fibonacci for example, if you use recursion without optimization, it’s too complicated to do a lot of repeated calculations.
But with mnemonization you can kind of think of it as a layer of caching, where you save the evaluated value and you can use it the next time you come across it.
The Fibonacci code to achieve mnemonized search is:
static long F(int n,long record[])
{
if(n==1||n==2) {return 1; }if(record[n]>0)
return record[n];
else
record[n]=F(n-1,record)+F(n-2,record);
return record[n];
}
public static void main(String[] args) {
int n=6;
long[] record = new long[n+1];
System.out.println(F(n,record));
}
Copy the codeAnd the dynamic programming way you can do it logically from front to back, starting with the third dp each dp is the sum of the first two.
public int fib(int n) {
int dp[]=new int[n+1];
dp[0] =0;
dp[1] =1;
for(int i=2; i<n+1; i++){ dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];
}
Copy the codeOf course dynamic programming can also have a lot of spatial optimizations, some of which are only used once, and you can replace them with some variables. Some two-dimensional arrays are large and can be replaced with one-dimensional arrays. Of course, the dynamic planning topic is very big, there are a lot of such as tree DP, dp, backpack problems and so on often appear in the competition, the ability is limited here will appear some written test high-frequency dynamic planning!
Maximum sum of continuous subarrays
Given an integer array nums, find a contiguous subarray with the maximum sum (the subarray contains at least one element) and return the maximum sum.
Example:
Input: [– 2, 1, 3, 4, 1, 2, 1, 5, 4] output: 6: continuous subarray and maximum of [4, 1, 2, 1], is 6.
The dp method is the O(n) method. If dp[I] represents the sum of the largest sequence ending in the ith, and the equation of state of this dp is:
dp[0]=a[0]
dp[i]=max(dp[i-1]+a[i],a[i])
Copy the codeIf a previous maximum subsequence sum is greater than 0, then the element is joined, otherwise the element is independent.
The implementation code is:
public int maxSubArray(int[] nums) {
int dp[]=new int[nums.length];
int max=nums[0];
dp[0]=nums[0];
for(int i=1; i<nums.length; i++) { dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);
if(dp[i]>max)
max=dp[i];
}
return max;
}
Copy the codePs: What is the maximum sum of arrays that can be discontinuous? You think about enumerating positive earnings, that question is meaningless.
Maximum product of continuous subarrays
Given an array of integers, nums, find the contiguous subarray with the largest product (that subarray contains at least one number) and return the product of that subarray.
Example:
Input: [2,3,-2,4] output: 6 explanation: the subarray [2,3] has a maximum product of 6.
Maximum product of continuous subarrays, this is also a classic dynamic programming problem, but a little different from ordinary dynamic programming.
If all of the data is non-negative, the maximum product of contiguous arrays is treated in a similar way to the maximum sum of contiguous subarrays, either multiplied by the previous one or separated by its own portal.
dp[0]=nums[0]
dp[i]=max(dp[i-1]*a[i],a[i])
Copy the codeBut it’s going to be a negative number, times a negative number and it’s going to go from maximum to minimum, and it’s going to be a negative and it’s going to be maximum again.
How do you think about it?
Easy, we open two DPS, one dpmax[] records the maximum value of the product and one dpmin[] records the minimum value of the product. Then dpmax and DPmin are updated each time regardless of whether the current value is positive or negative. So we can record the maximum absolute value of the product through these two arrays.
Dynamic equations are also easy
dpmax[i]=max(dpmax[i-1]*nums[i],dpmin[i-1]*nums[i],nums[i])
dpmin[i]=min(dpmax[i-1]*nums[i],dpmin[i-1]*nums[i],nums[i])
Copy the codeA DPMIN can be understood by looking at a process that acts as an intermediate transition, recording possible negative extremes in case they are needed. The result is still the value in DPmax.
Longest increasing subsequence
The longest increasing subsequence, also known as LIS, is one of the dynamic programming algorithms that occurs at very high frequencies. Here on the stress buckle 300
Given an integer array nums, find the length of the longest strictly increasing subsequence.
A subsequence is a sequence derived from an array that deletes (or does not delete) the elements of the array without changing the order of the rest of the elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].
Input: nums = [0,1,0,3,2,3] output: 4 explanation: the longest increasing subsequence is [0,1,2,3], so the length is 4.
For longest incrementing subsequences, if you don’t consider dynamic programming, using violent enumerations is actually a bit more cumbersome, because you don’t know whether to incrementally increase something larger than the previous element.
For example, 1, 10, 3, 11, 4, 5, this sequence can’t pick 1, 10, 11 because 1, 3, 4, 5 is the largest, so the time complexity of violence enumerating all the cases is still very high.
Dp [I] is the longest increasing sequence ending in nums[I]. Dp [I] is the longest increasing sequence ending in nums[I]. Dp [I] is the longest increasing sequence ending in nums. Such time complexity is O(n2).
The state transition equation is:
Dp [I]= Max (dp[j])+1, 0≤j< I and num[j]<num[I]Copy the codeThe specific process is:
The implementation code is:
class Solution {
public int lengthOfLIS(int[] nums) {
int dp[]=new int[nums.length];
int maxLen=1;
dp[0] =1;
for(int i=1; i<nums.length; i++){int max=0;// Count the longest increasing substring with the last digit smaller than itself
for(int j=0; j<i; j++){/ / the enumeration
// The end number is smaller than the current number and the length is longer than the longest record
if(nums[j]<nums[i]&&dp[j]>max){
max=dp[j];
}
}
dp[i]=max+1;// The longest prefix is the self
if(maxLen<dp[i])
maxLen=dp[i];
}
returnmaxLen; }}Copy the codeBut there’s an optimization to this problem, which is order nlogn.
We use dp to record the length of the longest sequence ending in nums[I]. Globally, we want the length to be as small as possible with the same length!
For example 2,3,9,5… The longest length in front is 3 and we’re willing to throw away 2,3,9 and use all 2,3,5. That is, for a value, we want that value to update the last value of the longest sequence ending in it.
If this value does not update the longest sequence, try updating the second-longest trailing value to prevent it from being used. For example, the sequence 2,3,9,5,4,5 updates 2,3,9; Then 2,3,4 updates 2,3,5 to pave the way for the longest 2,3,4,5.
The core of this idea is to maintain an array of Lenth [], length[I] indicates the minimum value at the end of the subsequence of length I, because we increase the value by one length each time, the value is larger than the previous one (fully compared), so the array is also increasing, increasing, Then dichotomy optimization can be used when updating the tail value of the maximum length sequence at the locked position.
The implementation code is:
class Solution {
public int lengthOfLIS(int[] nums) {
int length[]=new int[nums.length];
int len=1;
length[0]=nums[0];
for(int i=1; i<nums.length; i++){int left=0,right=len;
while (left<right){
int mid=left+(right-left)/2;
if(length[mid]<nums[i]){
left=mid+1;
}else {
right=mid;
}
}
length[left]=nums[i];
if(right==len)
len++;
}
returnlen; }}Copy the codeLongest common subsequence
The longest common subsequence also becomes LCS. Very frequent!
Given two strings text1 and text2, return the length of the longest common subsequence of the two strings. If no common subsequence exists, return 0.
A subsequence of a string is a new string made up of the original string without changing the relative order of the characters by deleting some characters (or none).
For example, “ace” is a subsequence of “ABCDE”, but “AEC” is not a subsequence of “ABCDE”. A common subsequence of two strings is a subsequence that is shared by both strings.
Take b, C, d, d, e and a, C, e, e, d, e. The common substring is c, d, e. If you use violence, the complexity is too high and you simply timeout, you need to use dynamic programming. Two strings match, we set up the two-dimensional dp[][] array, dp[I][j] represents the length of the longest common substring at the ith end of Text1 and the JTH end of Text2.
The core here is to understand the state transition and analyze the transition situation of DP [I][j]. When it reaches I and J:
Text1 [I]==text2[j], because both elements are in the last position, so the match must be successful, in other words, the neighbor dp value of this position cannot be greater than it (at most equal). So this is dp[I][j]=dp[I -1][j-1] +1;
If text1 [I]! = text2 [j], there are two possibilities, we know the neighbors have a dp [j], [I – 1] dp [I] [1], a lot of people will think of dp [I – 1] [1] this must be less than or equal to than the previous two, because is the scope of the front two child! Dp [I][j]= Max (dp[I][j-1],dp[i-1][j]).
So the whole state transition equation is:
dp[i][j] = dp[i-1][j-1] + 1 / / text1 [I] = = text2 [j]
dp[i][j] = max(dp[i][j-1],dp[i-1][j]) //text1[i]! = text2 [j]
Copy the codeThe implementation code is:
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
char ch1[]=text1.toCharArray();
char ch2[]=text2.toCharArray();
int dp[][]=new int[ch1.length+1][ch2.length+1];
for(int i=0; i<ch1.length; i++) {for(int j=0; j<ch2.length; j++) {if(ch1[i]==ch2[j])
{
dp[i+1][j+1]=dp[i][j]+1;
}
else
dp[i+1][j+1]=Math.max(dp[i][j+1],dp[i+1][j]); }}returndp[ch1.length][ch2.length]; }}Copy the codeLongest common substring
Given two strings str1 and str2, print the longest common substring of the two strings.
For example, the longest common substring of abceef and a2b2cee3f is cee. A common substring is the longest consecutive portion of the same part of two strings.
How do you analyze it? Similar to the analysis of the longest common subsequence above, dynamic programming matching is required, and logically simpler processing, as long as the current I,j do not match then dp value is 0, if it can match then dp[i-1][J-1] + 1
The state transition equation of the core is:
dp[i][j] = dp[i-1][j-1] + 1 / / text1 [I] = = text2 [j]
dp[i][j] = 0 //text1[i]! = text2 [j]
Copy the codeI’m not going to write anything like this, but there’s a problem with some of them telling you to print the longest string or something like that, and you have to remember to store values in some variable.
Different subsequence
Different subsequences also occur, and they’re a little bit more difficult, as you can see from the previous analysis of different subsequences.
Given a string s and a string t, count the number of occurrences of t in a subsequence of S.
A subsequence of strings is a new string formed by deleting some (or none) characters without interfering with the relative positions of the remaining characters. (For example, “ACE” is a subsequence of “ABCDE”, but “AEC” is not)
Example:
Input: s = "rabbbit", t = "rabbit" Output: 3 Explanation: As shown below, there are 3 ways to get "rabbit" from S. Arrow symbols on (^) characters that selecting rabbbit ^ ^ ^ ^ ^ ^ rabbbit ^ ^ ^ ^ ^ ^ rabbbit ^ ^ ^ ^ ^ ^Copy the codeQ: How many Pats are fixed and short? A: How many pats are fixed and short? But the length of the t string is not fixed, so we’re going to use arrays instead of if else.
Dp [j] = t string [0,j-1] = t string [0,j-1] = t string [0,j-1] = t string [0,j-1] = t string [0,j-1] = t string [0,j-1] = t string [0,j-1] Each element in the s string is compared to all elements in the T string to see if it is equal, if the string that the s string enumerates is equal to the JTH element in the T string. The dp [j + 1) + = dp [j]. You may ask why dp[j+1], because the first element matches the number +1, but to avoid this judgment we set dp[0]=1, so that each element of the T string will operate normally.
However, it is important to note that when traversing the i-th letter in the S-string, the t-string cannot be traversed from left to right, but must be traversed from right to left. Because traversing the i-th character of s string requires that the data at the moment be a relatively static superposition (i.e. the same level does not have an effect), and the same character encountered from left to right will have an effect on the following values. For the difference, please refer to the following example:
The code is as follows:
class Solution {
public int numDistinct(String s, String t) {
char s1[]=s.toCharArray();
char t1[]=t.toCharArray();
int dp[]=new int[t1.length+1];
dp[0] =1;// it is used to stack
for(int i=0; i<s1.length; i++) {for(int j=t1.length-1; j>=0; j--) {if(t1[j]==s1[i])
{
dp[j+1]+=dp[j]; }}}returndp[t1.length]; }}Copy the codeconclusion
At this point, simple dynamic programming is shared.
Most of the simple dynamic programming is tricky, and if you see an array problem or a string problem, there’s a good chance that dynamic programming is hidden. The routine of dynamic programming is a little similar to recursion, mainly to find the equation of state transition, sometimes can not think too much in one step (thinking too much may be involved in), and dynamic programming is to ask everyone to understand the relationship between numerical up and down conversion calculation.
For complex DP problems or many sets of a shell is really difficult to see, but master the above common DP problems and knapknack problems, can solve most of the dynamic programming problems (after all, we are not in competition or simple or medium difficulty).
Original is not easy, for a three even! Recently, I organized my original articles into a PDF book of data structures and algorithms regularly updated maintenance, follow my public account [Bigsai] reply [666] can be obtained.