Niuke programming problem -- dynamic programming of must brush 101 (a thorough understanding of dynamic programming)

Supplementary knowledge

Basic concepts ： Dynamic programming （Dynamic Programming,DP） It's a branch of operations research , It is the process of solving the optimization of decision-making process .

Purpose ： The dynamic programming problem is ⼀ The general form is Find the maximum value .

Problem solving ideas ：
1、 Break down big problems
2、 Based on this minimal structure, we can deduce , , in turn, Get a relationship between solutions at different levels . It's a bit like mathematical induction . It is to express the relationship between the steps you split with mathematical formulas , This formula is easy to implement with recursion .
3、 Consider the boundaries ： To use recursion , Then we have to consider the boundary problem .

Three elements of dynamic planning ：

• Optimal substructure , The smallest step of splitting mentioned above .
• The border , When it comes to recursion, we must consider .
• State transition equation , The relationship between unsynchronization during splitting .【 a key 】

Thinking framework ： clear 「 state 」 -> Definition dp Array / The meaning of function -> clear 「 choice 」-> clear base
case.

The basic idea ： The problem to be solved is decomposed into several interrelated subproblems , First solve the subproblem , Then we get the solution of the original problem from the solutions of these subproblems ; For recurring subproblems , Only solve it at the first encounter , And save the answers , Let's quote the answer directly when we encounter it again in the future , There is no need to solve again . Dynamic programming algorithm regards the solution of the problem as the result of a series of decisions

1、 Fibonacci sequence

Direct recursive method is enough

public class Solution {
    
    public int Fibonacci(int n) {
    
        if(n <=2){
    
            return 1;
        }else
            return Fibonacci(n-1)+ Fibonacci(n-2); 
    }
}

Writing code is simple and easy to understand , however ⼗ It's inefficient , Where is the inefficiency ⾥？ hypothesis n = 20, Please draw a recursive tree .

How to understand this recursive tree ？ That is to say, we want to calculate the original problem f(20) , I have to work out first ⼦ problem f(19) and f(18) , And then calculate f(19) , I have to work out first ⼦ problem f(18) and f(17) , And so on . Finally, I met f(1) perhaps f(2) When , The result is known , You can return the result directly , The recursive tree no longer goes down ⽣⻓ 了 .

The time complexity of the algorithm ： Number of sub questions * （ Single sub problem time ）= O(2^n)
The time complexity of this algorithm is , Index level , The explosion .

The reason why the algorithm is inefficient ： There is ⼤ Repeat the calculation ,⽐ Such as f(18) Was counted twice ,⽽ And you can see , With f(18) The recursive tree for the root is huge ⼤, Count more ⼀ All over , It's going to cost a lot of ⼤ Time for .

The nature of dynamic programming problem ： overlap ⼦ problem

The optimization process 1（ Array ）

thought ： In fact, the idea is very simple , Save the results of each round of calculation to the array , Then return the result , Each time you encounter a sub problem, first look it up in the array , If it has been calculated , Just use it directly .

int fib(int N) {
    
	if (N < 1) return 0;
	//  The array is fully initialized to  0
	vector<int> memo(N + 1, 0);
	//  Initialize the simplest case 
	return helper(memo, N);
}
int helper(vector<int>& memo, int n) {
    
	// base case
	if (n == 1 || n == 2) return 1;
	//  Calculated 
	if (memo[n] != 0) return memo[n];
		memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
	return memo[n];
}

Will put ⼀ There is a huge amount of redundant recursive tree through 「 prune 」, Transformed into ⼀ A recursive graph without redundancy , extremely ⼤ Less ⼦ problem （ That is, the nodes in the recursive graph ） The number of .

The time complexity of this algorithm is O(n)
This solution is almost the same as iterative dynamic programming , It's just this ⽅ The law is called 「⾃ Top down 」, Dynamic planning is called 「⾃ Bottom up 」

What is called? 「⾃ Top down 」？
It's going up and down , from ⼀ It's on a larger scale ⼤ The original problem of ⽐ If you say f(20) , Break down the scale gradually , straight
To f(1) and f(2) Touch bottom , Then go back to the answer level by level , This is called 「⾃ Top down 」.

What is called? 「⾃ Bottom up 」？
In turn, , We go straight from the bottom , The most simple , The scale of the problem is the largest ⼩ Of f(1) and f(2) Start pushing up , Until we get the answer we want f(20), This is the idea of dynamic planning , That's why dynamic programming ⼀ It's all out of recursion ,⽽ It's iterated by loops Complete the calculation .

The optimization process 2（dp surface ）

In fact, the idea and optimization process 1 It's the same , From this table, from bottom to top

int fib(int N) {
    
	vector<int> dp(N + 1, 0);
	// base case
	dp[1] = dp[2] = 1;
	for (int i = 3; i <= N; i++)
		dp[i] = dp[i - 1] + dp[i - 2];
	return dp[N];
}

The optimization process 3

According to the state transition of Fibonacci sequence ⽅ cheng , The current state is only related to the previous two states , It doesn't have to be that ⻓
Of ⼀ individual DP table To store all the States , Just find a way to store the previous two states ⾏ 了 . therefore , You can enter ⼀ Step optimization , Reduce space complexity to O(1)：

int fib(int n) {
    
	if (n == 2 || n == 1)
		return 1;
	int prev = 1, curr = 1;
	for (int i = 3; i <= n; i++) {
    
		int sum = prev + curr;
		prev = curr;
		curr = sum;
	}
	return curr;
}

2、 The problem of collecting change

Title Description ： Here you are. k Kind of ⾯ Worth a coin ,⾯ Values, respectively c1, c2 … ck , The number of coins of each kind ⽆ limit , Give again ⼀ A total ⾦ forehead amount , You need at least ⼏ Two coins to make this ⾦ forehead , If it is impossible to come up with , The algorithm returns -1

⽐ If you say k = 3 ,⾯ Values, respectively 1,2,5, total ⾦ forehead amount = 11 . So at least 3 A coin makes up , namely 11 = 5 + 5 + 1.

Recurrence of violence ：

1、 Find the optimal substructure

Supplementary content ： Must conform to 「 The optimal ⼦ structure 」,⼦ Problems must be independent of each other ⽴
Illustrate with examples ： The original question is the most ⾼ The total score of , So your ⼦ The problem is to put ⽂ Get the most ⾼, Get the most in math ⾼……
In order to get the most in every course ⾼, You should get the most scores for the corresponding multiple-choice questions in each course ⾼, Fill in the blanks and get the most ⾼…… Of course , In the end, you get full marks in every class , This is the most ⾼ The total score of .
Got the right result ： most ⾼ The total score is the total score . Because this process is optimal ⼦ structure ,“ Every subject ⽬ Get the most ⾼” these ⼦ The problem is to be independent of each other ⽴, Not each other ⼲ Disturbing .

The current problem ： Back to collecting change , Why is it optimal ⼦ Structure ？⽐ If you want to ask amount =11 Minimum number of coins per hour （ The original question ）, If you know how to come up with amount = 10 The minimum number of coins （⼦ problem ）, You just need to ⼦ The answer to the question plus ⼀（ Choose again ⼀ gold ⾯ The value is 1 The coin of ） It's the answer to the original question , Because there is no limit to the number of coins ,⼦ There is no mutual restriction between the problems , It's mutual independence ⽴ Of .

2、 How to list the correct state transitions ⽅ cheng ？

• Make sure the 「 state 」, That is, the original problem and ⼦ Variables that change in the problem . Due to the number of coins ⽆ limit , So only ⼀ The state of is ⽬ mark ⾦ forehead amount .
• Then determine dp Definition of function ： Current ⽬ mark ⾦ Well, yes n ,⾄ Don't need dp(n) A coin makes up the ⾦ forehead .
• Then determine 「 choice 」 And choose the best , That is, for each state , What choices can be made to change the current state .

The current problem ：⽆ On when ⽬ mark ⾦ How much is it , The choice is from ⾯ List of credits coins Choose from ⼀ A coin , then ⽬ mark ⾦ The amount will be reduced ：

#  Pseudo code frame 
def coinChange(coins: List[int], amount: int):
	#  Definition ： We need to make it up ⾦ forehead  n,⾄ Less  dp(n)  A coin 
	def dp(n):
	#  To make a choice , Choose the result that needs the least coins 
		for coin in coins:
			res = min(res, 1 + dp(n - coin))
		return res
	#  The question we ask is  dp(amount)
	return dp(amount)

• Finally, make it clear that base case, obviously ⽬ mark ⾦ The forehead is 0 when , The number of coins required is 0; When ⽬ mark ⾦ forehead ⼩ On 0 when ,⽆ Explain , return -1：

def coinChange(coins: List[int], amount: int):
	def dp(n):
		# base case
		if n == 0: return 0
		if n < 0: return -1
		#  Seeking the best ⼩ value , So initialize to positive ⽆ poor 
		res = float('INF')
		for coin in coins:
			subproblem = dp(n - coin)
			# ⼦ problem ⽆ Explain , skip 
			if subproblem == -1: continue
			res = min(res, 1 + subproblem)
		return res if res != float('INF') else -1
	return dp(amount)

State shift ⽅ Cheng has actually finished , The above algorithm is already critical ⼒ It's solved , The mathematical form of the above code is state transition ⽅ cheng ：
$$dp(n)=\{\begin{array}{l}0,n=0\\ -1,n<0\\ \min \{dp(n-\mathrm{coin})+1\mid \mathrm{coin}\in \text{ coins }\},n>0\end{array}$$

Continue to optimize ： Eliminate overlapping sub problems 【⽐ Such as amount = 11, coins = {1,2,5} Draw a recursive tree to see ：】

Use arrays to eliminate overlapping subproblems

def coinChange(coins: List[int], amount: int):
	memo = dict()
	def dp(n):
		#  consult a dictionary , Avoid double counting 
		if n in memo: return memo[n]
		if n == 0: return 0
		if n < 0: return -1
		res = float('INF')
		for coin in coins:
			subproblem = dp(n - coin)
			if subproblem == -1: continue
			res = min(res, 1 + subproblem)
		#  remember ⼊ In the dictionary 
		memo[n] = res if res != float('INF') else -1
		return memo[n]
	return dp(amount)

Use dp Table to eliminate overlapping subproblems

dp[i] = x  surface ⽰, When ⽬ mark ⾦ The forehead is  i  when ,⾄ Don't need  x  Coin .
int coinChange(vector<int>& coins, int amount) {
    
	//  Array ⼤⼩ by  amount + 1, The initial value is also  amount + 1
	vector<int> dp(amount + 1, amount + 1);
	// base case
	dp[0] = 0;
	for (int i = 0; i < dp.size(); i++) {
    
		//  Inner layer  for  Asking for all ⼦ problem  + 1  The most ⼩ value 
		for (int coin : coins) {
    
			// ⼦ problem ⽆ Explain , skip 
			if (i - coin < 0) continue;
			dp[i] = min(dp[i], 1 + dp[i - coin]);
		}
	}
	return (dp[amount] == amount + 1) ? -1 : dp[amount];
	}

Specific topic ：

Change money ( One )

Title Description ：

• Given array arr, arr All values in are positive integer ring repetition
• arr Each value in represents - - Seed surface Value currency , Any currency of any denomination may be used
• form aim The minimum number of currencies
• If there is no solution , Please return -1

This is the problem of collecting change , Specific solutions ： Dynamic programming
Specific steps ：
step1: It can be used dp[i] It means that the minimum amount of money is needed to make up yuan .
step2: It is set to the maximum value at the beginning aim + 1, So the currency is the smallest 1 element , That is, the number of currencies will not exceed aim.
step3: initialization dp[0]= 0.
step 4: Subsequent traversal 1 Yuan to aim element , Enumerate the possible composition of each denomination of currency , Take the minimum value of each time , The transfer equation is dp[i] = min(dp[i],dp[i - arr[]] + 1).
step 5: Last comparison dp[aim] Whether the value of exceeds aim, If more than that, there is no solution , Otherwise, you can return .

 public int minMoney (int[] arr, int aim) {
    
        // write code here
        if(aim < 1) return 0; 
        //  Set maximum aim+1, The number of currencies will not exceed aim
        int [] dp = new int[aim+1];
        // dp[i] Means to gather together i How much money does yuan need 
        Arrays.fill(dp,aim+1);
        //  initialization 
        dp[0] = 0;
        for(int i=1; i<= aim;i++){
    
            for(int j =0 ; j< arr.length; j++){
    
                if(arr[j] <= i) //  You can only use it if the face value does not exceed the amount you need to raise 
                    dp[i] = Math.min(dp[i],dp[i-arr[j]]+1);
            }
        }
        return dp[aim] > aim ? -1:dp[aim];   
    }

Complexity analysis :
● Time complexity : O(n.aim), The first layer traverses the enumeration 1 Yuan to aim element , The second layer traverses the enumeration n The face value of each currency
● Spatial complexity : O(aim), Auxiliary array dp Size

3、 Minimum cost of climbing stairs

Title Description ： Given an array of integers cost , among cost[i] It's from the stairs i The cost of climbing a step up , Subscript from 0 Start . Once you pay this fee , You can choose to climb up one or two steps .
You can choose from the subscript to 0 Or subscript 1 The steps began to climb the stairs .
Please calculate and return the minimum cost to reach the top of the stairs .

Example
Input ：[1,100,1,1,1,90,1,1,80,1]
Return value ：6
explain ：
You will subscript 0 The steps begin .
1. payment 1 , Climb up two steps , The arrival subscript is 2 The steps of .
2. payment 1 , Climb up two steps , The arrival subscript is 4 The steps of .
3. payment 1 , Climb up two steps , The arrival subscript is 6 The steps of .
4. payment 1 , Climb up a step , The arrival subscript is 7 The steps of .
5. payment 1 , Climb up two steps , The arrival subscript is 9 The steps of .
6. payment 1 , Climb up a step , Get to the top of the stairs .
The total cost is 6 .

Ideas ： Dynamic programming
The topic also examines the dynamic programming implementation of Fibonacci series , The difference is that the topic requires the minimum cost , Therefore, when we recurse the scheme statistics, we can only record the minimum cost scheme .

Specific steps ：
step 1： You can use an array to record every time you climb to the i Minimum cost of stairs , Then the state will be transferred once every step is added , The final result .
step 2：（ The initial state ） Because it can be directly from the 0 Grade or grade 1 The steps begin , Therefore, the cost of these two levels is directly 0.
step 3：（ State shift ） One step at a time , There are only two cases , Or it takes a step up the front step , Or two steps up the first two steps , Because of the cost on the front steps, we all got , Therefore, the minimum value can be updated every time , The transfer equation is ：dp[i]=min(dp[i−1]+cost[i−1],dp[i−2]+cost[i−2])

public int minCostClimbingStairs (int[] cost) {
    
        //  Total number of stairs ,dp[i] It means to climb to the first i The order requires the least cost 
        int[] dp = new int[cost.length+1];
        for(int i = 2; i<= cost.length;i++){
    
            dp[i] = Math.min(dp[i-1] + cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[cost.length];
    }

4、 Longest common subsequence ( Two )

Given two strings str1 and str2, Output the longest common subsequence of two strings . If the longest common subsequence is empty , Then return to "-1". Data given so far , There will only be one longest common subsequence

Input ：“1A2C3D4B56”,“B1D23A456A”
Return value ：“123456”

Their thinking ： Dynamic programming

1、 Thought analysis

Common sequence
Want to find s1 and s2 Public sequence of , If any characters are equal s1[i] == s2[j], that s1[0…i-1] and s2[0…j-1] The common sequence of plus equal characters , You can get a longer common sequence , So there is , Make s[i][j] Indicates that they are respectively matched to i,j A common sequence of

for(int i = 0; i < s1.length();i++){
    
    for(int j = 0;j < s2.length();j++){
    
        if(s1[i] == s2[j]){
     //  Matching character 
            s[i][j] = s[i-1][j-1] + s1[i]; //  Previous splice   New character 
        }else{
     //  When you don't match 
            s[i][j] = s[i][j-1] or s[i-1][j]; //  Choose one of the two 
        }
    }
}

The longest
In the above scheme , Guaranteed to be a public sequence , But no control for the longest

Consider increasing the length of the comparison , To choose a better length s

for(int i = 0; i < s1.length();i++){
    
    for(int j = 0;j < s2.length();j++){
    
        if(s1[i] == s2[j]){
     //  Matching character 
            if(s[i-1][j-1].length() + 1 > s[i][j].length()){
     //  Longer 
            	s[i][j] = s[i-1][j-1] + s1[i]; //  Previous splice   New character 
            }
        }else{
     //  When you don't match 
            if(s[i][j-1].length() > s[i][j].length()){
     //  Longer 
                s[i][j] = s[i][j-1];
            }
            if(s[i-1][j].length() > s[i][j].length()){
     //  Longer 
                s[i][j] = s[i-1][j];
            }
        }
    }
}

Space optimization
The disadvantages of the above scheme are , Copy the string again and again , The total complexity reaches O(n3)

Since only in s1[i]==s2[j] Add characters only when , So consider , Record each of the above s The last one of s Coordinates of , So when you finally need an answer , Directly along the coordinate relationship , Output when equal

Boundary treatment

The main boundary here is the boundary of operation , So initialize one of them with a length of 0 At the time of the dp zero

for(int i = 0;i<=s1.size();i++){
     
    dp[i][0] = 0;
}
for(int i = 0;i<=s2.size();i++){
    
    dp[0][i] = 0;
}

=========================================================================
If... Has been given A and B, We can use LCS(x, y) Express A and B Of LCS length , Let's find the recursive relation .
1、

2、 If A and B The trailing characters are the same

3、 If it's not the same

4. The boundary of recurrence formula

5. Complete recurrence formula

Specific steps ：
step 1： Priority is given to special cases .
step 2： Dynamic programming can be used to obtain the length of the longest common subsequence , We use dp[i][j]dp[i][j]dp[i][j] It means that s1 China and Israel iii ending ,s2 China and Israel jjj The longest common subsequence length of the ending string .
step 3： Traverse all positions of two strings , Start state transition ： if iii Bit and jjj The characters of bits are equal , Then the problem can become 1+dp[i−1][j−1]1+dp[i-1][j-1]1+dp[i−1][j−1], That is, the length of the longest common subsequence up to this point is added by the previous result 1.
step 4： If it's not equal , Explain the substring up to this point , The last bit cannot belong to the longest common subsequence at the same time , After all, they are different , So we consider changing to two subproblems ,dp[i][j−1]dp[i][j-1]dp[i][j−1] perhaps dp[i−1][j]dp[i-1][j]dp[i−1][j], Let's take the larger one , This feeling can be solved recursively .
step 5： But recursion is too complex , A lot of low-level parts are recalculated , So we can use dynamic programming , From front to back , This forms a table , Table from position 1 Start adding back , Just in line with the transfer characteristics of dynamic programming .
step 6： Because the sequence will be returned at last , Not the length , Therefore, while constructing the table, another two-dimensional matrix should be used to record the direction selected during the above state transition , We use it 1 From the top left ,2 From the left ,3 From the top .
step 7： When getting this sequence , According to start from the last , According to the recorded direction , Assemble characters recursively and forward , Add this character only when it comes from the top left , This is because two characters are equal in dynamic programming , Only when the characters are equal .

import java.util.*;

public class Solution {
    
    /** * longest common subsequence * @param s1 string character string  the string * @param s2 string character string  the string * @return string character string  */
    private String x = "";
    private String y = "";
    
    //  Get the longest subsequence 
    private String ans(int i,int j,int[][] b){
    
        String res = "";
        //  Recursive termination condition 
        if(i==0 || j==0)
            return res;
        //  According to the direction , Forward recursion , Add characters 
        if(b[i][j] == 1){
    
            res += ans(i - 1, j - 1, b);
            res += x.charAt(i - 1);
        }
        else if(b[i][j] == 2)
            res += ans(i - 1, j, b);
        else if(b[i][j] == 3)
            res += ans(i,j - 1, b);
        return res;
    }
    
    
    public String LCS (String s1, String s2) {
    
        // write code here
        if(s1.length() == 0 || s2.length() == 0)
            return "-1";
        int len1 = s1.length();
        int len2 = s2.length();
        x = s1;
        y = s2;
        // dp[i][j] Represents the first string number i position , Second string j Bit represents the length of the longest common subsequence 
        int [][] dp = new int[len1 + 1][len2 + 1];
        //  The direction of dynamic programming addition 
        int [][] b = new int[len1 + 1][len2 + 1];
        //  Traverse two positions to find the longest length 
        for(int i = 1; i<=len1; i++){
    
            for(int j = 1;j <=len2; j++){
    
                if(s1.charAt(i-1) == s2.charAt(j - 1)){
    
                    //  Consider moving forward one of the two 
                    dp[i][j] = dp[i -1][j-1]+1;
                    b[i][j] = 1;
                }
                //  The two characters are different 
                else{
    
                    //  The choice on the left is bigger , That is, the first string goes back by one digit 
                    if(dp[i-1][j] > dp[i][j-1]){
    
                        dp[i][j] = dp[i-1][j];
                        //  On the left 
                        b[i][j] = 2;
                    }
                    //  The choice on the right is bigger , That is, the second string goes back one bit 
                    else{
    
                        dp[i][j] = dp[i][j-1];
                        //  From above 
                        b[i][j] = 3;
                    }
                }
            }
        }
        //  Get the answer string 
        String res = ans(len1,len2,b);
        //  Check if the answer is empty 
        if(res.isEmpty())
            return "-1";
        else
            return res; 
    }
}

5、 The longest public substring

Title Description : Given two strings str1 and str2, Output the longest common substring of two strings
Title assurance str1 and str2 The longest common substring of exists and is unique

Input ： “1AB2345CD”,“12345EF”
Return value ： “2345”

Pay attention to distinguish the longest common substring And the longest common subsequence ： Subsequence It could be discontinuous , but Substring It must be continuous .

Dynamic programming

Definition dp[i][j] Representation string str1 pass the civil examinations i Characters and str2 Species j Characters are the longest common substring formed by the last element . If required dp[i][j], That is to say str1 Of the i Characters and str2 Of the j Characters are the longest common substring formed by the last element , We first need to determine whether the two characters are equal .

• If it's not equal , Then they can't form a common substring , That is to say dp[i][j]=0;
• If equal , We also need to calculate the number of preceding equal characters , In fact, that is dp[i-1][j-1], therefore dp[i][j]=dp[i-1][j-1]+1;
  
  We have the recurrence formula , The code is simpler , We use two variables , A common substring with the longest record , The end position of the longest common substring of a record , Finally, you can intercept the string , So let's look at the code

Specific steps ：
step 1： We can use dp[i][j] It means that str1 In order to i Characters ending in str2 In order to j The length of the common substring at the end of characters ,
step 2： Iterate through two string fills dp Array , The transfer equation is ： If the two characters of the bit traversed are equal , Then the length at this time is equal to the length of the previous two digits +1,dp[i][j]=dp[i−1][j−1]+1, If the two characters are not equal when traversing to this bit , Is set to 0, Because this is a substring , Must be continuously equal , Disconnect to restart .
step 3： Each update dp[i][j] after , We maintain the maximum , And update the end position of the substring .
step 4： Finally, the substring can be intercepted according to the end position of the maximum value .

import java.util.*;


public class Solution {
    
    /** * longest common substring * @param str1 string character string  the string * @param str2 string character string  the string * @return string character string  */
    public String LCS (String str1, String str2) {
    
        //  Record length 
        int maxlength = 0;
        int maxLastIndex = 0;
        int [][] dp = new int[str1.length() + 1][str2.length() + 1];
        for(int i = 0; i< str1.length();i++){
    
            for(int j = 0; j < str2.length();j++){
    
                if(str1.charAt(i) == str2.charAt(j)){
    
                    dp[i+1][j+1] = dp[i][j]+1;
                    // If a longer substring is encountered , To update , Record the length of the longest substring ,
                    // And the position of the last element of the longest substring 
                    if(dp[i+1][j+1] > maxlength){
    
                        maxlength = dp[i+1][j+1];
                        maxLastIndex = i;
                    }
                } else{
    
                    // The recursive formula , When two characters are not equal 
                    dp[i+1][j+1] = 0;
                }
            }
        }
        // Most strings are intercepted ,substring(a,b) in a and b Indicates the start and end positions of interception respectively 
        return str1.substring(maxLastIndex - maxlength + 1, maxLastIndex + 1);
        
    }
}

6、 Number of different paths ( One )

Title Description ： A robot is in m×n The upper left corner of the size map （ The starting point ）.
The robot can move down or right at a time . The robot will reach the lower right corner of the map （ End ）.
How many different paths can you take from the beginning to the end ？

Example
Input ：2,1
Return value ：1
Input ：2,2
Return value ：2

recursive

specific working means :
First, when we are in the first grid in the upper left corner , There are two ways to walk : If you go right , It is equivalent to the following one (n - 1) * m To find the number of different paths from the upper left corner to the lower right corner ; And if you go down , It is equivalent to the following one n * (m - 1) To find the different number of paths from the upper left corner to the lower right corner . and (n - 1) * m The matrix of and n * (m - 1) The matrices of are n *m Matrix subproblem , So you can use recursion .
step 1:( Termination conditions ) When the matrix gets longer n Reduced to 1 When , It is obvious that we can only go down , There's no other choice , Only 1 Paths ; Empathy m Reduced to 1 It's the same when . Therefore, the returned quantity is 1.
step 2:( Return value ) For each level, the results returned from its two sub problems are added and returned to the upper level .
step 3:( Tasks at this level ) Each level has two path choices: down or right , Enter the subproblem of the corresponding branch respectively .

public int uniquePaths (int m, int n) {
    
        //  recursive 
        if(m ==1 || n == 1){
    
            return 1;
        }
        //  Down  (m-1) * n  towards the right  m *(n-1) 
        return uniquePaths(m-1,n) + uniquePaths(m , n-1);
    }

Complexity analysis :

• Time complexity :O(mn), among m、n Are the lengths of both sides of the matrix , Recursive procedure for each m At most, we have to go through every kind of n
• Spatial complexity :O(mn), The maximum depth of the recursive stack

Dynamic programming

If we are in the lower right corner of the grid , Then the path to the grid can only be the two grids above it and to its left , Therefore, the number of paths from the upper left corner to the lower right corner should be the sum of the number of paths from the upper left corner to its left lattice and upper lattice , So it can be dynamically planned .
step 1: use dp [i][j] The size is i* j The number of paths to the matrix , Subscript from 1 Start .
step 2:( Initial conditions ) When i perhaps j by 1 When , The representation matrix has only one row or one column , So there is only one path .
step 3:（ Transfer equation ) The number of paths in each grid will only come from the number of grids on its left and the number of grids on its top , So the state transition is dp[i][j] = dp[i -1][j]＋dp[i][j-1].

public int uniquePaths (int m, int n) {
    
        //  Dynamic programming 
        //dp[i][j] Express ⼤⼩ by i*j The number of paths to the matrix 
        int[][] dp = new int[m+1][n+1];
        for(int i = 1;i <= m;i++){
    
            for(int j = 1 ; j<=n; j++){
    
                if(i==1 || j ==1){
    
                    dp[i][j]=1;
                    continue;
                }
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m][n];
    }

Complexity analysis :

• Time complexity :O(n), The calculation process needs to start from 1 Traversing n
• Spatial complexity :O(1), Constant level variable , No additional auxiliary space

7、 The minimum path sum of matrices

Title Description ： Given a n * m Matrix a, Starting from the upper left corner, you can only go right or down at a time , Finally reach the lower right corner , All the numbers on the path add up to the path and , Output the smallest of all paths and .

for example ： When the input [[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]] when , The corresponding return value is 12,
The selected minimum sum path is shown in the figure below ：

Example 1
Input ：[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]
Return value ：12
Example 2
Input ：[[1,2,3],[1,2,3]]
Return value ：7

Dynamic programming

design idea :

Define a dp The size is n×m matrix , among dp[i][j] The value of represents walking to (i,j) The minimum path of and .
When i = 0, j = 0 when ,dp[i][j] = matrix [i][j]
When i = 0,j != 0 when , dp[i][j] = dp[0][j-1] +matrix[0][j]
When i != 0,j = 0 when , dp[i][j] = dp[i-1][0] +matrix[i][0]
When i != 0, j != 0 when , dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j] The last return value is dp[n-1][m-1].
Finally, the return value dp[n-1][m-1]

Specific steps ：
step 1: We can construct a two-dimensional auxiliary array of the same size as the matrix , among dp[][j] Said to (i,j) The shortest path whose position is the end point and , be dp[0][0]= matria[0][0].
step 2: It's easy to know the first row and the first column , Only right or down , There is no second option , So the first row can only be accumulated by the left side , The first — Columns can only be accumulated by the above .
step 3: After the edge state is constructed , ergodic matrix , Complete each position in the matrix dp Array value : If the current position is (i,j), The last step is either (i-1,j) Down , Either it's (i,j One 1) To the right , Then the sum of the smaller value and the value of the current position is the minimum path to the current position , So the state transition formula is dp[i][j]=min(dp[i -1][j], dp[i][j-1])+matria[i][i].
step 4: Last move to (n - 1, m —1) The position of is the shortest path to the lower right corner and .

public int minPathSum (int[][] matrix) {
    
        //  That's ok 、  Column 
        int n = matrix.length;
        int m = matrix[0].length;
        int[][] dp = new int[n+1][m+1];
        dp[0][0] = matrix[0][0]; // dp[i][j]  Said to i,j The shortest path length with the position as the end point 
        for(int i =1;i<n;i++) //  Process the first column 
            dp[i][0] = matrix[i][0] + dp[i-1][0];
        for(int i =1;i<m;i++) //  Deal with the first line 
            dp[0][i] = matrix[0][i] + dp[0][i-1];
        for(int i = 1; i< n;i++){
    
            for(int j = 1; j<m;j++){
    
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + matrix[i][j];
            }
        }
        return dp[n-1][m-1];

8、 Translate numbers into strings

Title Description ： There is a way to code letters into numbers ：‘a’->1, ‘b->2’, … , ‘z->26’.
We encode a string into a string of numbers , Then consider reverse compiling into a string .
Because there is no delimiter , Encoding numbers into letters may have a variety of compilation results , for example 11 It can be seen as two ‘a’ It can also be seen as a ‘k’ . but 10 Can only be ‘j’ , because 0 Can't compile into any results .
Now give a string of numbers , Returns the number of possible decoding results

Input ：“12”
Return value ：2
explain ：2 Possible decoding results （”ab” or ”l”）

Input ： “31717126241541717”
Return value ： 192
explain ： 192 Possible decoding results

Dynamic programming

For normal arrays 1-9, There is only one decoding method , But for 11-19,21-26, There are two alternative decoding schemes , Therefore, we use dynamic programming to accumulate the two schemes .

Specific steps ：
step 1： Use auxiliary array dp Before presentation i How many decoding methods are there
step 2： For a number , We can decode it directly , It can also be compared with the previous 1 perhaps 2 Combine to decode ： If you decode directly , be dp[i]=dp[i−1]; If combined decoding , be dp[i]=dp[i−2]
step 3： There is only one decoding method , Select a species dp[i−1] that will do , For satisfying two decoding methods （10,20 You can't ） It is dp[i−1]+dp[i−2]
step 4： Add... In turn , final dp[length] That's the answer .

public class Solution {
    
    /** *  decode  * @param nums string character string   Digital string  * @return int integer  */
    public int solve (String nums) {
    
        //  Dynamic programming 
        if(nums.equals("0"))
            return 0;
        if(nums.equals("10")|| nums.equals("20"))
            return 1;
        //  When 0 It's not in front of 1 and 2
        for(int i=1;i<nums.length();i++){
    
            if(nums.charAt(i) =='0')
                if(nums.charAt(i-1) !='1' && nums.charAt(i-1) !='2')
                    return 0;
        }
        int [] dp = new int[nums.length()+1];
        // Initialize auxiliary array 1
        Arrays.fill(dp,1);
        for(int i=2; i<=nums.length();i++){
    
            if(nums.charAt(i-2) == '1' && nums.charAt(i-1) !='0' || nums.charAt(i-2) == '2' && nums.charAt(i-1) >'0'&& nums.charAt(i-1) <'7' )
                dp[i] = dp[i-1] + dp[i-2];
            else
                dp[i] = dp[i-1];
            
        }
        return dp[nums.length()];
    }
}

9、 Longest ascending subsequence ( One )

Title Description ： Given a length of n Array of arr, Find the length of its longest strictly ascending subsequence .
So called subsequences , It refers to deleting some numbers from an array （ It's also possible to delete ） after , New array formed . for example [1,5,3,7,3] Array , Its subsequences are ：[1,3,3]、[7] etc. . but [1,6]、[1,3,5] Is not its subsequence .

Input ：[6,3,1,5,2,3,7]
Return value ：4
explain ： The longest ascending subsequence of the array is [1,2,3,7] , The length is 4

Dynamic programming

To find the longest increasing subsequence length , Whenever we find a place , Is it a subsequence that continues to increase or not , It selects the first place before it can reach the longest increasing subsequence , The common method of this kind of state transition problem is dynamic programming .
Specific steps ：
step 1： use dp[i] Representation to element iii At the end , The length of the longest subsequence , Initialize to 1, Because only arrays have elements , At least one is incremental .
step 2： The first layer traverses each position of the array , obtain n A subarray of length .
step 3： The second layer traverses the corresponding subarray to find the corresponding element iii The longest increment sequence length at the end , Maximum during maintenance .
step 4： For each to iii At the end of the subarray , If an element is encountered during traversal j Less than the closing element , It shows that the subsequence ending with this element plus the last element of the subarray is also strictly incremental , So the transfer equation is dp[i]=dp[j]+1.

public int LIS (int[] arr) {
    
        //  Dynamic programming 
        int[] dp = new int[arr.length +1];
        Arrays.fill(dp,1);
        int res = 0;
        for(int i=1;i< arr.length;i++){
    
            for(int j=0;j<i;j++){
    
                if(arr[i]> arr[j] && dp[i]< dp[j]+1){
    
                    dp[i] = dp[j]+1;
                    res = Math.max(res, dp[i]);
                }
            }
        }
        return res;
    }

10、 The maximum sum of successive subarrays

Title Description ： Enter a length of n Integer array array, One or more consecutive integers in an array form a subarray , The minimum length of the subarray is 1. Find the maximum sum of all subarrays .

Example
Input ：[1,-2,3,10,-4,7,2,-5]
Return value ：18
explain ： It can be seen from the analysis , Subarray of input array [3,10,-4,7,2] The maximum sum can be obtained as 18

Their thinking ： Because there are positive and negative charges in the array 0, So one number at a time , Do you want to add it to the continuous subarray we are looking for , It's a problem. , It's possible that it will be bigger , It's possible to join a smaller , And we want a continuous maximum , Therefore, this kind of stateful transition problem can be considered as dynamic programming .

Specific steps ：
step 1： It can be used dp The array represents the following symbol iii Is the largest continuous subarray of the end point and .
step 2： Traversal array , Each time a new array element is encountered , Successive subarrays are either added to become larger , Or the element itself is bigger , Or even smaller , We give up when we are younger , So the state transition is dp[i]=max(dp[i−1]+array[i],array[i])
step 3： Because contiguous arrays may break , Each segment can only get the maximum value of that segment , So we need to maintain a maximum .

import java.util.*;

public class Solution {
    
    public int FindGreatestSumOfSubArray(int[] array) {
    
        //  Dynamic programming 
        int[] dp = new int[array.length +1];
        int res = array[0];
        dp[0] = array[0];
        for(int i=1;i < array.length;i++){
    
            dp[i] = Math.max(dp[i-1] + array[i], array[i]);
            //  Save the maximum value that appears 
            res = Math.max(res,dp[i]);
        }
        return res;
    }
}

11、 Longest text substring

Title Description ： For length is n A string of A（ Only numbers , Case letters ）, Please design an efficient algorithm , Calculate the length of the longest palindrome substring .

Example
Input ：“ababc”
Return value ：3
explain ： The longest palindrome substring is "aba" And "bab", The length is 3

Greedy thinking belongs to a kind of dynamic programming thought , The basic principle is to find the optimal solution of each local substructure in the whole , And finally combine all these local optimal solutions to form an optimal solution as a whole .

Ideas ： Palindrome string , It has the characteristics of left-right symmetry , Visit together from beginning to end , The elements encountered are the same . But here we are looking for the longest palindrome string , The length is not known in advance , What do I do ？ The process of judging palindromes is from the beginning to the end to the middle , Then we can find the longest palindrome string in reverse , From the middle to the end , This is it. The central expansion method .

Specific steps ：
step 1： Traverses each character of the string .
step 2： Take the characters traversed each time as center （ There are two cases: odd length and even length ）, Continue to expand to both sides .
step 3： If both sides are the same, it is palindrome , It is the character that expands to the maximum length （ Or even two ） The longest palindrome string at the center .
step 4： We compare the longest palindrome substring centered on each character , Take the maximum value .

import java.util.*;


public class Solution {
    
    /** *  The class name in the code 、 Method name 、 The parameter name has been specified , Do not modify , Return the value specified by the method directly  * * * @param A string character string  * @return int integer  */
    
    //  The center point starts to expand 
    private int fun(String s, int begin,int end){
    
        while(begin >= 0 && end < s.length() && s.charAt(begin) == s.charAt(end)){
    
            begin--;
            end ++;
        }
        return end - begin -1;
    }
  
    public int getLongestPalindrome (String A) {
    
        //  The central expansion method 
        int [] dp = new int[A.length()+1];
        int maxlen = 1;
        //  The initial value is set to 1
        Arrays.fill(dp,1);
        for(int i=0;i<A.length()-1;i++){
    
            // Divide odd length and even length to extend to both sides 
            dp[i] = Math.max(dp[i],Math.max(fun(A,i,i),fun(A,i,i+1))); 
            //  Save the maximum value 
            maxlen = Math.max(maxlen,dp[i]);
        }
        return maxlen;
    }
}

 Compact version --- It doesn't need to be dp

```java
import java.util.*;
public class Solution {
    
    public int fun(String s, int begin, int end){
    
        // Each center point starts to expand 
        while(begin >= 0 && end < s.length() && s.charAt(begin) == s.charAt(end)){
     
            begin--;
            end++;
        }
        // Return length 
        return end - begin - 1; 
    } 
    public int getLongestPalindrome (String A) {
    
        int maxlen = 1;
        // Center on each point 
        for(int i = 0; i < A.length() - 1; i++) 
            // Divide odd length and even length to extend to both sides 
            maxlen = Math.max(maxlen, Math.max(fun(A, i, i), fun(A, i, i + 1))); 
        return maxlen;
    }
}

12、 The number string is converted into IP Address

Title Description ： Now there is a string that contains only numbers , Convert the string to IP The form of address , Return to all possible situations .
for example ：
The given string is "25525522135",
return [“255.255.22.135”, “255.255.221.35”]. ( The order doesn't matter )

enumeration

Ideas ： about IP character string , If there are only numbers , Is equivalent to the need for us to IP Three points of the address are inserted into the string , The position of the first point can only be in the first character 、 Second character 、 After the third character , The second point can only be after the first point 1-3 Within four positions , The third point can only be after the second point 1-3 Within four positions , And the number after the third point shall not exceed 3, because IP Each address has a maximum of 3 Digit number .

specific working means ：
step 1： Enumerate the positions of these three points in turn .
step 2： Then cut out four numbers .
step 3： Compare the intercepted figures , Not greater than 255, Besides 0 There can be no leading 0, Then it can be assembled into IP Add the address to the answer .

 public ArrayList<String> restoreIpAddresses (String s) {
    
        //  Violence solution -- enumeration 
        ArrayList<String> res = new ArrayList<>();
        int n = s.length();
        //  Traverse the first point 
        for(int i =1; i<4 && i< n-2; i++){
    
            //  Second points 
            for(int j = i+1; j< i+4 && j < n-1;j++){
    
                // The third point 
                for(int k = j+1; k < j+4 && k < n; k++){
    
                    //  The remaining figures in the last paragraph do not exceed 3
                    if(n-k >=4)
                        continue;
                    //  Intercept 
                    String a = s.substring(0,i);
                    String b = s.substring(i,j);
                    String c = s.substring(j,k);
                    String d = s.substring(k);
                    
                    //  The judgment number is not greater than 255
                    if(Integer.parseInt(a) > 255 ||Integer.parseInt(b) > 255 ||Integer.parseInt(c) > 255||Integer.parseInt(d) > 255)
                        continue;
                    //  Exclude leading 0
                    if((a.length() != 1 && a.charAt(0) == '0') || (b.length() != 1 && b.charAt(0) == '0') ||  (c.length() != 1 && c.charAt(0) == '0') || (d.length() != 1 && d.charAt(0) == '0'))
                        continue;
                    // assemble 
                    String temp = a + "." + b + "."+ c + "." + d;
                    res.add(temp);
                }
            }
        }
        return res;
    }

recursive + to flash back

Recursion is a method in which a procedure or function directly or indirectly calls itself in its definition or description , It usually transforms a large and complex problem into a smaller problem similar to the original problem to solve . So recursive process , The most important thing is to see if the original problem can be broken down into smaller sub problems , This is the key to using recursion .

Ideas ： about IP The address takes out one number and one dot at a time , The rest can be considered as a sub problem , So you can use recursive and backtracking pruning to insert points into numbers .

import java.util.*;

public class Solution {
    
    /** * * @param s string character string  * @return string character string ArrayList */
    ArrayList<String> res = new ArrayList<>();
    ArrayList<String> ip = new ArrayList<>();
   
    public ArrayList<String> restoreIpAddresses (String s) {
    
        // write code here
        dfs(s, 0);
        return res;
    }
    
    public void dfs(String s , int start){
    
        if(ip.size() == 4 && start == s.length()){
    
            //  Legal solution 
            res.add(ip.get(0) + '.' + ip.get(1) + '.' + ip.get(2) + '.'+ ip.get(3));
            return;
        }
        if(s.length() - start > 3 *(4 - ip.size())) //  prune , The total cut length is greater than 12, Or each segment is greater than 3
            return;
        if(s.length() - start < (4- ip.size())) //  prune , The total cut length is less than 4, Or each segment is less than 0
            return;
        int num = 0;
        for(int i= start; i< start + 3 && i<s.length(); i++){
    
            num = num * 10 + (s.charAt(i) - '0'); // ip Value of each segment 
            if(num < 0 || num > 255)
                continue;
            ip.add(s.substring(start, i+1));
            
            dfs(s, i+1);
            ip.remove(ip.size() -1);
    
            if(num == 0) //  Prefix... Is not allowed 0
                break;
        }
        
    }
}

13、 Edit distance ( One )

Title Description ： Given two strings str1 and str2 , Please calculate the str1 To str2 The minimum number of operands .
You can change the string 3 Kind of operation ：
1. Insert a character
2. Delete a character
3. Change a character .

Example 1
Input ：“nowcoder”,“new”
Return value ：6
explain ：“nowcoder”=>“newcoder”( take ’o’ Replace with ’e’), Modify the operating 1 Time "nowcoder"=>“new”( Delete "coder"), Delete operation 5 Time
Example 2
Input ：“intention”,“execution”
Return value ：5
explain ： One scheme is : because 2 Both lengths are 9, hinder 4 The length of each suffix is "tion", So from the "inten" To "execu" Modify one by one

Dynamic programming

Ideas ： Change the first string into the second string , We need to turn the substring of the first string into the second string one by one with the least operation , This involves increasing the length of the first string , State shift , Then consider dynamic programming . use dp[i][j] Indicates that from the beginning of two strings to str1[i] and str2[j] Edit distance required for substring up to , That's obvious dp[str1.length][str2.length] Is the editing distance we require .（ Subscript from 1 Start ）

Specific steps ：
step 1： Initial conditions ： Suppose the second string is empty , It is obvious that every additional character in the first string substring , Edit the distance by adding 1, This step is to delete ; Empathy , Suppose the first string is empty , Every additional character in the second string , The writer's distance increases 1, This step is to add .
step 2： State shift ： The state transition is definitely going to dp The matrix is filled with , Then go through each length of the first string , Corresponds to each length of the second string . If you traverse to str1[i] and str2[j] The location of , The two characters are the same , There is no need to operate the extra characters , The number of operations is the same as the previous one of the two substrings , So there is dp[i][j]=dp[i−1][j−1]; If the two characters are different , Then these two characters need to be edited , But the shortest distance at this time is not necessarily to modify the last bit , It is also possible to delete a character or add a character , Therefore, we choose the minimum value of the three cases to increase the editing distance , namely dp[i][j]=min(dp[i−1][j−1],min(dp[i−1][j],dp[i][j−1]))+1.
Icon ：

 public int editDistance (String str1, String str2) {
    
        //  Use dynamic programming 
        int n1 = str1.length();
        int n2 = str2.length();
        //  Set up dp[i][j], Indicates that from the beginning of two strings to str1[i] and str2[j] Edit distance required for substring up to 
        int[][] dp = new int[n1+1][n2+1];
        //  Judge boundary condition , Assume the second string is empty 
        for(int i = 1 ; i<= n1;i++)
            dp[i][0] = dp[i-1][0] +1;
        //  Judge boundary condition , Suppose the first string is empty 
        for(int i = 1 ; i<= n2;i++)
            dp[0][i] = dp[0][i-1] +1;
        //  Except the initialization boundary 
        for(int i=1;i<=n1;i++){
    
            for(int j=1;j<=n2;j++){
    
                //  Make a state transition , Determine whether two strings are equal , If equal , Characters don't have to be manipulated 
                if(str1.charAt(i-1) == str2.charAt(j-1))
                    dp[i][j] = dp[i-1][j-1];
                else
                    dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1; 
            }
        }
        return dp[n1][n2];
    }

14、 Regular Expression Matching

Title Description ： Please implement a function to match including ’.‘ and ’‘ Regular expression of .
1. Characters in pattern ’.‘ Represents any character
2. Characters in pattern ’' Indicates that the character in front of it can appear any number of times （ contain 0 Time ）.
In the subject , Matching means that all characters of a string match the whole pattern . for example , character string "aaa" With the model "a.a" and "abaca" matching , But with the "aa.a" and "ab*a" No match

Example ：
Input ：“aaa”,"aa"
Return value ：true
explain ： In the middle of the Can occur any number of times a, So you can see 1 Time a, To match

Ideas ：
If it's only lowercase , Then directly compare whether the characters are the same to match , If there is one more ’.‘, You can use it to match any character , As long as it corresponds to str If the element in is not empty . But more ’*' character , There are many situations , Involving state transition , So we use dynamic programming .

Specific steps ：
step 1： set up dp[i][j] Express str front i Characters and pattern front j Whether characters match .（ You need to pay attention to the i,j It's length. , More than the corresponding string subscripts 1）

step 2：（ Initial conditions ） First , Beyond all doubt , Two empty strings are directly matched , therefore dp[0][0]=true. Then we assume str The string is empty , that pattern How can I match an empty string ？ The answer is to use ’‘ The character appears 0 Secondary characteristics . Traverse pattern character string , If you encounter ’' It means that the characters in front of it can appear 0 Time , To match an empty string, there can only be 0, That's equivalent to considering whether the previous character can match , therefore dp[0][i]=dp[0][i−2].

step 3： （ State shift ） Then traverse str And pattern Each length of , Start looking for state transitions . First, consider that the character is not ’‘ Simple situation of , As long as the two characters traversed are equal , or pattern In the string is ’.‘ To match , So the last bit matches , That is, check whether the previous one of the two can complete the matching , namely dp[i][j]=dp[i−1][j−1]. Then consider ’' What happened ：

• pattern[j - 2] == ‘.’ || pattern[j - 2] == str[i -1]： namely pattern The previous one can match one more , It can be used ’*' Let it appear one more time or not , So there's a transfer equation dp[i][j]=dp[i−1][j]∣∣dp[i][j−2]
• Not meeting the above conditions , Can only not match , Let the previous character appear 0 Time ,dp[i][j]=dp[i][j−2]
  

import java.util.*;
public class Solution {
    
    public boolean match (String str, String pattern) {
    
        int n1 = str.length();
        int n2 = pattern.length();
        //dp[i][j] Express str front i Characters and pattern front j Whether characters match 
        boolean[][] dp = new boolean[n1 + 1][n2 + 1]; 
        // Traverse str Each length 
        for(int i = 0; i <= n1; i++){
      
            // Traverse pattern Each length 
            for(int j = 0; j <= n2; j++){
     
                // The case of empty regularity 
                if(j == 0){
     
                    dp[i][j] = (i == 0 ? true : false);
                // In case of non empty   asterisk 、 Order number 、 character 
                }else{
     
                    if(pattern.charAt(j - 1) != '*'){
    
                        // The current character is not *, use . To match or match characters directly 
                        if(i > 0 && (str.charAt(i - 1) == pattern.charAt(j - 1) || pattern.charAt(j - 1) == '.')){
    
                            dp[i][j] = dp[i - 1][j - 1];
                        }
                    }else{
    
                        // meet *
                        if(j >= 2){
    
                            dp[i][j] |= dp[i][j - 2];
                        }
                        // If the previous one is . Or the previous digit can match this number 
                        if(i >= 1 && j >= 2 && (str.charAt(i - 1) == pattern.charAt(j - 2) || pattern.charAt(j - 2) == '.')){
    
                            dp[i][j] |= dp[i - 1][j];
                        }
                    }
                }
            }
        }
        return dp[n1][n2];
  }
}

15、 Longest bracket substring

Title Description ： Give a length of n Of , Contains only characters ‘(’ and ‘)’ String , Calculate the length of the longest correctly formatted bracket substring .

example 1: For strings “(()” Come on , The longest well formed substring is “()” , The length is 2 .
example 2： For strings “)()())” , Come on , The longest well formed substring is “()()” , The length is 4 .

For the problem of bracket matching , Stack can be preferred , Through the principle of "first in, last out"

Stack

Ideas ： Because the brackets need to match one by one , And the first left parenthesis , Only the following closing parenthesis can be matched , Therefore, you can consider using the stack's first in and last out function , Match parentheses .

Specific steps ：
step 1： You can use the stack to record the left parenthesis subscript .
step 2： Traversal string , Left bracket in stack , Each time the right bracket is encountered, the subscript of the left bracket will pop up .
step 3： Then the length is updated to the distance between the current subscript and the subscript at the top of the stack .
step 4： Inconsistent parentheses encountered , May make the stack empty , So you need to use start Record the last ending position , Subtract... From the current subscript start You can get the length , The substring is obtained .
step 5： The maximum length of the last maintained substring in the loop .

public int longestValidParentheses (String s) {
    
        //  Stack 
        int res = 0;
        int start = -1;
        Stack<Integer> st = new Stack<Integer>();
        for(int i=0;i<s.length();i++){
    
            // Left parenthesis encountered , Direct stack 
            if(s.charAt(i)== '(')
                st.push(i);
            //  Right parenthesis encountered 
            else{
    
                // If the stack is empty when closing the parenthesis , illegal , Set to end position 
                if(st.isEmpty())
                    start = i;
                else{
    
                    //  Pop up the left bracket 
                    st.pop();
                    if(!st.empty())
                        // There are also left parentheses in the stack , The right bracket is not enough , Subtracting the top of the stack is the length 
                        res = Math.max(res, i - st.peek());
                    else
                        res = Math.max(res, i- start);   
                }
            } 
        }
        return res; 
    }

Dynamic programming

The length of substring , Involving state transition , Use the dynamic programming method directly
specific working means ：
step 1： use dp[i]dp[i]dp[i] Indicates that the following is marked as i The character of is the longest legal bracket length of the end point .
step 2： It's obvious that the left parenthesis can't be the end , So the left parentheses are all dp[i]=0dp[i]=0dp[i]=0.
step 3： We traverse the string , Because the first place is either the left bracket or the right bracket dp Arrays are all 0, So skip , We will only look at the right parenthesis later , There are two cases of closing parentheses ：

As shown in the figure , Next to the left bracket is the right bracket , Then the legal brackets need to be added 2, It is possible to add... On the basis before this pair of parentheses , Maybe this pair is the starting point , So the transfer formula is ：dp[i]=(i>=2?dp[i−2]:0)+2

As shown in the figure , The left bracket that matches the right bracket is not next to itself , But before the legal sequence before it , Therefore, the first matching left parenthesis can be obtained by subtracting the legal sequence length of the previous one from the subscript , So the transfer formula is ：dp[i]=(i−dp[i−1]>1?dp[i−dp[i−1]−2]:0)+dp[i−1]+2

public int longestValidParentheses (String s) {
    
        //  Dynamic programming 
        int res = 0;
        if(s.length() == 0 || s == null)
            return res;
        //dp[i] Indicates that the following is marked as i The character of is the longest legal bracket length of the end point 
        int[] dp = new int[s.length()+1];
        // First, whether the left bracket or the right bracket is 0, So don't worry 
        for(int i=1;i<s.length();i++){
    
            if(s.charAt(i) == ')'){
    
                if(s.charAt(i-1)=='(')
                    dp[i] = (i>=2 ? dp[i-2]:0) +2;
                else if(i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(')
                     dp[i] = (i - dp[i - 1] > 1 ? dp[i - dp[i - 1] - 2] : 0) + dp[i - 1] + 2;
            }
            res = Math.max(res,dp[i]);
        }
        return res;  
    }

16、 raid homes and plunder houses ( One )

Title Description ： You are an experienced thief , Ready to steal a row of rooms along the street , Each room has a certain amount of cash , To prevent detection , you You can't steal two adjacent houses , namely , If you steal the first one , You can't steal a second house ; If you steal a second house , Then you can't steal the first and third .
Given an array of integers nums, The elements in the array represent the amount of cash in each room , Please calculate the maximum amount of theft without being found .

Input ： [1,2,3,4]
Return value ： 6
explain ： The best solution is to steal the second 2,4 A room

Ideas ： Some people may think that the use of greed , Just steal the most money from others , Either even or odd number of all the money , But sometimes in order to steal more money , Maybe they will give up two companies without stealing , So this scheme is not feasible , We still consider dynamic programming .

Specific steps ：
step 1： use dp[i] The length is i Array of , How much money can you steal at most , As long as each transition state is gradually accumulated, you can get the money that the whole array can steal .
step 2：（ The initial state ） If the array length is 1, Only one family , It must have stolen the family , The most profitable , therefore dp[1]=nums[0].
step 3：（ State shift ） Every time for a family , We choose to steal him or not , If we choose to steal, then the previous one must not steal , Therefore, the maximum benefit of the accumulated superior , Similarly, if you choose not to steal him , Then we can accumulate up to one level of income . So the transfer equation is dp[i]=max(dp[i−1],nums[i−1]+dp[i−2]). there i stay dp Array length in , stay nums Middle is the subscript .

public int rob (int[] nums) {
    
        //  Dynamic programming 
        int [] dp = new int[nums.length+1];
        //  The length is 1 , Choose the first one directly 
        dp[1] = nums[0];
        for(int i=2;i<=nums.length;i++)
            dp[i] = Math.max(dp[i-1],nums[i-1]+dp[i-2]);
        
        return dp[nums.length];
    }

17、 raid homes and plunder houses ( Two )

Title Description ： The rooms along the lake form a A closed circle , That is, the first room and the last room are considered adjacent .
Given a length of n Array of integers for nums, The elements in the array represent the amount of cash in each room , Please calculate the maximum amount of theft without being found .
difference ： The array is circular , The first and last are adjacent , Stole the first one , The last one can't steal , And vice versa .

Ideas ： This problem is related to home raiding ( One ) similar , The difference is that the problem is circular , The first and last are adjacent , In that case , In the original plan, the first and the last can't get... At the same time .

Specific steps ：
step 1： Using the original scheme is ： use dp[i] The length is i Array of , How much money can you steal at most , As long as each transition state is gradually accumulated, you can get the money that the whole array can steal .

step 2：（ The initial state ） If the array length is 1, Only one family , It must have stolen the family , The most profitable , therefore dp[1]=nums[0].

step 3：（ State shift ） Every time for a family , We choose to steal him or not , If we choose to steal, then the previous one must not steal , Therefore, the maximum benefit of the accumulated superior , Similarly, if you choose not to steal him , Then we can accumulate up to one level of income . So the transfer equation is dp[i]=max(dp[i−1],nums[i−1]+dp[i−2]). there i stay dp Array length in , stay nums Middle is the subscript .

step 4： At this time, the first house and the last house cannot get , Then we can discuss it in two situations ：
situation 1： Steal money from the first house , Don't steal the last family's money . The initial state and state transition remain unchanged , Only when traversing, the last bit of the array is not traversed .
situation 2： Steal the last one please , Don't steal money from the first house . The initial state is set dp[1]=0, Not the first one , Then, when traversing, it will also traverse to the last bit of the array .

step 5： Finally, take the larger value of the two cases .

import java.util.*;


public class Solution {
    
    /** *  The class name in the code 、 Method name 、 The parameter name has been specified , Do not modify , Return the value specified by the method directly  * * * @param nums int Integer one-dimensional array  * @return int integer  */
    public int rob (int[] nums) {
    
        // write code here
        int[] dp = new int[nums.length+1];
        //  Choose the first 
        dp[1] = nums[0];
        for(int i = 2;i<nums.length;i++){
    
            dp[i] = Math.max(dp[i-1],dp[i-2]+ nums[i-1]);
        }
        int res = dp[nums.length-1];
        //  Don't choose the first one 
        Arrays.fill(dp,0);
        dp[1] = 0;
        for(int i = 2;i<= nums.length;i++){
    
            dp[i] = Math.max(dp[i-1],dp[i-2]+ nums[i-1]);
        }
        return Math.max(res, dp[nums.length]);
        
    }
}

18、 The best time to buy and sell stocks ( One )

Title Description ：
Suppose you have an array prices, The length is n, among prices[i] Is the stock in the second i Sky price , Please use this price array , Returns the maximum return you can get from buying and selling stocks
1. You can buy stocks once and sell stocks once , You can't buy or sell once a day , You can only buy and sell once in all , And the buying must be one day before the selling
2. If you can't make any profit , Please return 0
3. Assuming that there is no service charge for buying and selling

Example
Input ：[8,9,2,5,4,7,1]
Return value ：5
explain ： In the 3 God ( Stock price = 2) Buy when , In the 6 God ( Stock price = 7) Sell when , Maximum profit = 7-2 = 5 , You can't choose on page 2 Sky buying , The first 3 Day sell , This is a loss 7 了 ; meanwhile , You can't sell stocks before buying

Greedy Algorithm

Ideas ：
1、 Use variables to record historical lowest prices minprice
2、 In the first place i The profit from selling stocks in one day is prices[i] - minprice
3、 therefore , We just need to traverse the price array once , Record the lowest point in history

public int maxProfit (int[] prices) {
    
        //  One time traversal greedy algorithm 
        int res = 0;
        //  A special case 
        if(prices.length ==0)
            return res;
        //  Keep the price as low as possible 
        int min = prices[0];
        //  because min Is the first position , therefore i Directly from 1 Start 
        for(int i=1;i< prices.length;i++){
    
            min = Math.min(min,prices[i]);
            res = Math.max(res, prices[i]- min);
        }
        return res;
    }

Dynamic programming

Ideas ： For each day, there are two states: the maximum return so far and whether to hold shares , So we can use dynamic programming .

Specific steps ：
step 1： use dp[i][0] It means the first one i Day does not hold the maximum return until that day ,dp[i][1] It means the first one i Tian Holdings , Maximum gain to date .
step 2：（ The initial state ） Day one does not hold shares , Then the total income is 0,dp[0][0]=0; The first day , Then the total income is the cost of buying stocks , This is a negative number ,dp[0][1]=−prices[0].
step 3：（ State shift ） For every day after that , If you do not hold shares on that day , It may have been sold or not bought in the past few days , So the total income so far is the same as the previous day , It may also be sold on the same day , We choose the larger state dp[i][0]=max(dp[i−1][0],dp[i−1][1]+prices[i])
step 4： If shares are held on the same day , It may be that I bought stocks in the previous few days , Not sold that day , So the return is the same as the day before , It is also possible to buy on the same day , At this time, the stock price with negative return , The same is to select the maximum value ：dp[i][1]=max(dp[i−1][1],−prices[i]).

public int maxProfit (int[] prices) {
    
        int n = prices.length;
        //dp[i][0]dp[i][0]dp[i][0] It means the first one i Day does not hold the maximum return until that day ,dp[i][1]dp[i][1]dp[i][1] It means the first one i Tian Holdings , Maximum gain to date .
        int [][] dp = new int[n+1][2];
        //  Day one does not hold shares 
        dp[0][0] = 0;
        //  The first day 
        dp[0][1] = -prices[0];
        for(int i=1;i < prices.length;i++){
    
            // 1、 I sold it a few days ago , The total income is the same as the previous day 
            // 2、  Sell on the same day , The total income is from the previous day plus those sold 
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
            //  Shares held on the same day :1、 Not sold yet  2、 Buy on the same day 
            dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
        }
        //  Not holding shares on the last day 
        return dp[prices.length-1][0];  
    }

19、 The best time to buy and sell stocks ( Two )

Title Description ： Suppose you have an array prices, The length is n, among prices[i] It's a stock on the i Sky price , Please use this price array , Returns the maximum return you can get from buying and selling stocks

1. You can Buy and sell the stock many times , But before buying again, you must sell the previous shares
2. If you can't get benefits , Please return 0
3. Assuming that there is no service charge for buying and selling

Greedy Algorithm

Ideas ： In fact, if we want to get the maximum benefit , Just buy at a low price and sell at a high price , Because you can buy and sell many times . Use greedy thoughts ： As long as the price is increasing in a range , Then the difference in this range is the income we can get .
Specific steps :
step 1： Traversal array , As long as the next array is larger than the previous one , You can make a profit .
step 2： Add up the gains , Get the final result .

public int maxProfit (int[] prices) {
    
        // write code here
        int res = 0;
        for(int i=1;i < prices.length;i++){
    
            if(prices[i-1] < prices[i])
                res += prices[i] - prices[i-1];
        }
        return res;
    }

Dynamic programming

The difference from the above question is that you can buy and sell many times

Ideas ： But for every day, there are still two states: the maximum return and whether to hold shares , So we can still use dynamic programming .

step 1： use dp[i][0] It means the first one i Day does not hold the maximum return until that day ,dp[i][1]dp[i][1]dp[i][1] It means the first one i Tian Holdings , Maximum gain to date .
step 2：（ The initial state ） Day one does not hold shares , Then the total income is 0,dp[0][0]=0dp[0][0]=0dp[0][0]=0; The first day , Then the total income is the cost of buying stocks , This is a negative number ,dp[0][1]=−prices[0].
step 3：（ State shift ） For every day after that , If you do not hold shares on that day , It may have been sold or not bought in the past few days , So the total income so far is the same as the previous day , It is also possible to sell shares on the same day , We choose the larger state dp[i][0]=max(dp[i−1][0],dp[i−1][1]+prices[i]);
step4： If shares are held on the same day , It may be that the goods bought a few days ago have not been sold , So the return is the same as the day before , It is also possible to buy on the same day , Minus the cost of buying , The same is to select the maximum value ：dp[i][1]=max(dp[i−1][1],dp[i−1][0]−prices[i]))

The difference with the topic lies in the shareholding situation on that day ： Maximum dp[i][1]=max(dp[i−1][1],dp[i−1][0]−prices[i]))

public int maxProfit (int[] prices) {
    
        // write code here
        int n = prices.length;
        //dp[i][0]dp[i][0]dp[i][0] It means the first one i Day does not hold the maximum return until that day ,dp[i][1]dp[i][1]dp[i][1] It means the first one i Tian Holdings , Maximum gain to date .
        int [][] dp = new int[n+1][2];
        //  Day one does not hold shares 
        dp[0][0] = 0;
        //  The first day 
        dp[0][1] = -prices[0];
        for(int i=1;i < prices.length;i++){
    
            // 1、 I sold it a few days ago , The total income is the same as the previous day 
            // 2、  Sell on the same day , The total income is from the previous day plus those sold 
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
            //  Shares held on the same day :1、 Not sold yet  2、 Buy on the same day 
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0]-prices[i]);
        }
        //  Not holding shares on the last day 
        return dp[prices.length-1][0];  
    }

20、 The best time to buy and sell stocks ( 3、 ... and )

Title Description ： Suppose you have an array prices, The length is n, among prices[i] It's a stock on the i Sky price , Please use this price array , Returns the maximum return you can get from buying and selling stocks

1. You can have a maximum of Two transaction operations , A transaction represents a buy and a sell , But before buying again, you must sell the previous shares
2. If you can't get benefits , Please return 0
3. Assuming that there is no service charge for buying and selling

Example ：
Input ：[8,9,3,5,1,3]
Return value ：4
explain ： On the third day ( Stock price =3) buy in , The fourth day ( Stock price =5) sell , Yield is 2
Fifth day ( Stock price =1) buy in , Sixth days ( Stock price =3) sell , Yield is 2 The total revenue is 4.

difference ： Specify a maximum of two transaction operations

Dynamic programming

Ideas ： This question is related to the best time to buy and sell stocks （ One ） The difference is that you can buy and sell at most 2 Time , That's actually equivalent to a few more states , For every day, there are two states: the maximum return and the shareholding , The shareholding situation has been improved 5 Change , We use it ：
dp[i][0] To i The biggest gain from not buying stocks for days
dp[i][1] To i The maximum return from buying a stock but not selling it for days
dp[i][2] To i The maximum return from buying and selling stocks once a day
dp[i][3] To i The maximum return on stocks that have been bought twice and sold only once by the end of the day
dp[i][4] To i The maximum return on stocks bought twice and sold twice by the end of the day

Specific steps ：

• step 1：（ The initial state ） Similar to the questions mentioned above , The first 0 There are two states of buying and not buying ：dp[0][0]=0、dp[0][1]=−prices[0].
• step2： State shift ： For every subsequent day , If it is still the same day 0, The same as the previous day , There is no difference between ;
• step3： If the status of the day is 1, You may have bought it before or bought it for the first time on the same day , Select a larger value ：dp[i】[1]=max(dp[i−1][1],dp[i−1][0]−prices[i]);
• step4： If the status of the day is 2, That must be in 1 Under the state of （ Already bought once ） Sell for the first time on the same day , Or sell it long before you buy it for the second time , Select a larger value ：dp[i][2]=max(dp[i−1][2],dp[i−1][1]+prices[i]);
• step5： If the status of the day is 3, That must be in 2 Under the state of （ Has sold for the first time ） Bought the second time on the same day , Or buy the second time before , Just haven't sold yet , Select a larger value ：dp[i][3]=max(dp[i−1][3],dp[i−1][2]−prices[i]);
• step6： If the day is a state 4, That must be in 3 Under the state of （ Has bought the second time ） Sell for the second time on the same day , Or sell it for the second time before , Select a larger value ：dp[i][4]=max(dp[i−1][4],dp[i−1][3]+prices[i]).
• step 7： Finally, we will start from 0、 Sell... For the first time 、 Select the maximum value in the second sale , Because there may be no income , It is also possible to trade only once for the greatest return .

 public int maxProfit (int[] prices) {
    
        //  Dynamic programming 
        int n = prices.length;
        int [][] dp = new int[n+1][5];
        Arrays.fill(dp[0],-10000);
        //  The initial state , Not buying 
        dp[0][0] = 0;
        //  Initial purchase status 
        dp[0][1] = -prices[0];
        for(int i=1;i < n;i++){
    
            dp[i][0] = dp[i-1][0];
            //  Status as 1
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
            //  Status as 2
            dp[i][2] = Math.max(dp[i-1][1]+ prices[i], dp[i-1][2]);
            //  Status as 3
            dp[i][3] = Math.max(dp[i-1][3], dp[i-1][2] - prices[i]);
            //  Status as 4
            dp[i][4] = Math.max(dp[i-1][4], dp[i-1][3]+ prices[i]);
        }
        return Math.max(dp[n-1][2], Math.max(0,dp[n-1][4]));
    }
}

Forward and backward traversal

The title clearly states that at most two transactions can be made , And these two transactions are in chronological order （ You can hold up to one share at a time ）;

First assume that when two transactions are made , Gain the most , Suppose the first transaction is A, The second transaction is B; Trade A Occurs in a transaction B Before ;

Now we know A And B There must be no overlap in time （ Selling on the same day and buying on the same day are counted as no overlap ）, hypothesis A It happened on the second day 1_{i God , that B It must happen in the i}n God （ Ignore the buying and selling of the day ）;

So we can get the following formula ：
$$\max \text{ Profit }=\max \{f(1,i)+f(i,n)\}$$
According to the above formula , First, reverse traverse to find out from the i To the first day n Day maximum profit , Use a one-dimensional array to record （ The second transaction ）;

Then, forward traversal , Find the maximum profit （ The forward and reverse traversal order is not fixed , Switchable ）.

Look at the chestnuts below , You will find that for only one transaction , The situation of buying on the same day, selling on the same day and no trading meet the above formula ：

public int maxProfit (int[] prices) {
    
        //  Forward and backward traversal 
        int res = 0;
      //  There is only one element in the array or it is empty , return 0
      if (prices.length < 2){
    
          return res;
      }
      //  First, find out the maximum profit that can be obtained from the second transaction 
      // secondProfits[i] Says from the first i-1 The day begins 
      //  The maximum profit that can be made from a transaction at the end 
      int[] secondProfits = new int[prices.length];
      int len = prices.length-1;
      //  The maximum price 
      int max = prices[len];
      //  Go back and forth , The profit from buying and selling on the last day is 0
      for(int i = len - 1;i >= 0;--i){
    
          //  Update stock maximum 
          max = Math.max(max,prices[i]);
          //  Calculate from the second i-1 Maximum profit from day to day 
          secondProfits[i] = Math.max(secondProfits[i+1],
                                      max - prices[i]);
      }
      //  Minimum value of stock price when traversing from front to back 
      int min = Integer.MAX_VALUE;
      for (int i = 0;i < len;++i){
    
          //  Update the minimum stock price 
          min = Math.min(min,prices[i]);
          //  Find the most profitable combination of two transactions 
          res = Math.max(res,prices[i] -
                         min + secondProfits[i+1]);
      }
      return res;
    }