This article has participated in the good article call order activity, click to see: back end, big front end double track submission, 20,000 yuan prize pool for you to challenge!”

The weekend liver several dynamic planning questions, write my notes, the beginning of the story, the article step by step, if the viewer headache discomfort, hope to rest, but do not give up must read! Extra: each question has a unit test, see the officer direct copy can debug.

This article has been updated to Github

No.1

The simplest dynamic programming problem

My niece is 5 years old and now she starts to learn addition and subtraction. Every time she does math, she can’t do without her little fingers. If she is more than 5, she starts to count the fingers of the other hand

I asked her one day

“What’s 1+1+1+1+1?”

“Pick up little finger, start to count, five!”

“What about adding another one?”

“Six, of course.” – Blurt it out

“How did you get so fast this time?”

“That was just five. Add one to make six.”

“So you don’t have to recalculate because you remember the answer was 5! Dynamic programming is: you save time by remembering things from the past.”


Play, play, play. Don’t take it d p Kidding! \color{red}{don’t make fun of dp! }

Take a look at the entry for the Popular Science Encyclopedia of China

Dynamic Programming (DP) is a branch of operations research. It is the process of optimizing the decision-making process. In the early 1950s, THE American mathematician R.Bellman and others put forward the famous optimization principle when studying the optimization problem of the multi-stage decision process, thus creating the dynamic programming. Dynamic programming is widely used, including engineering technology, economy, industrial production, military and automation control and other fields, and has achieved significant results in the backpack problem, production and operation problem, capital management problem, resource allocation problem, shortest path problem and complex system reliability problem.

See not over of children’s shoes to skip, the hour we simple point

Actually, this is probably the easiest dynamic programming problem you can do.

What can we see about this problem?

We know that is the last step 1 will be calculated so fast, most thanks to calculate before the answer is 5, if we put the question as a child, I want to calculate the answer to every step, you can list an equation: f (x) = f (x – 1) + 1, everyone don’t to f (x) the mess, I put it as a simple way.

Where, f(x) is the value of which step, set an initial value, x > 0, then the first step

f(1) = 1;

f(2) = f(1) + 1;

.

f(6) = f(5) + 1

In the world of a program, what is used to store a data structure that can record the previous result values?

Obvious: arrays. We just use the subscripts to store the bashi, and that’s the dynamic in dynamic programming, which is to define some boundaries and initialize.

When you see this, iron, you can do dynamic programming. Let’s do problem number two.

No.2

Leecode 322: You have three kinds of coins, 2 yuan, 5 yuan and 7 yuan. There are enough coins for each. You need 27 yuan to buy a book

Why does it feel like we’re back in grade school word problems?

— Simple analysis: Minimal coin combination -> Use as large a coin as possible

Who came up with this stupid problem? It’s so easy

7+7+7=21,21+2+2+2=27, 6 coins

Oh my god

7+5+5+5+5=27, 5 coins

We can think about it in a very violent way, in a small way, it doesn’t add up to more than 27, for example

7+7+7+7 > 27 (Excluded)

7+7+7+5 or 7+7+7+ 2+2+2 6

.

Exhaustive is too slow and involves a lot of double counting, so what if I want the smallest coin combination of any value up to 27? Think about it.

Since the computer can hold the previous contents in memory, and it’s fast, obviously, we can open an array to hold the previous state.

Focus on early warning

1.1. Dynamic programming Component 1: Determining status

To put it simply, when solving dynamic programming, we need to open an array. What does each element of the array f[I] or f[I][j] stand for, similar to what does x, y, and z stand for in math

Solving dynamic programming requires two consciences:

  • The last step
  • subproblems

The last step

As we said in the first problem, the last step is 5. So in this case, even though we don’t know what the optimal strategy is, the optimal strategy must be K coins, A1, a2,…. The ak values add up to 27

So there must be a last coin :ak.

So minus this coin, the face value of the first coin adds up to 27 minus ak

Key point 1:

  • We don’t care how the first k-1 coin spelled 27-ak (there could be one or 100 ways to spell it), and we don’t even know ak and K yet, but we’re sure the first coin spelled 27-ak

Key point 2:

  • Because it’s the optimal strategy, it has to have the least number of coins to spell 27-AK, otherwise it’s not the optimal strategy

subproblems

  • So we asked: what is the minimum number of coins to spell 27-AK
  • The original question was what is the minimum number of coins to spell 27
  • We turned the original problem into a subproblem on a smaller scale: 27-AK
  • To simplify the definition, let’s say that state f of x is equal to the minimum number of coins to spell out x

Wait, we don’t know what ak is in the last quarter

  1. Obviously, the last coin can only be 2,5 or 7
  2. If ak is 2, f of 27 should be f of 27 minus 2 plus 1, where 1 is the last coin 2.
  3. If ak is 5, f of 27 should be f of 27 minus 5 plus 1, where 1 is the last coin 5.
  4. If ak is 7, f of 27 should be f of 27 minus 7 plus 1, where 1 is the last coin 7.

So using the fewest number of COINS = f (27) = min {f (27-2) + 1, f (27-5) + 1, + 1} f (27-7)

1.2. Dynamic Programming Component 2: Transfer equations

Let’s say state f of x is equal to the minimum number of coins to spell out x

For any x: f(x) = min{f(x-2)+1, f(x-5)+1, f(x-7)+1}

1.3. Dynamic Programming Component 2: Initial conditions and boundary cases

Ask questions

  1. What if x minus 2, x minus 5, and x minus 7 are less than 0?
  2. When does it stop?

1.3.1

If you can’t spell Y, define f[Y] = infinity

For example, f[-1], f[-2] = infinity

F [1]=min{f(-1)+1, f(-3)+1, f(-6)+1}

Initial condition: F [0] = 0

2.4. Dynamic programming Component 2: Computation sequence

Calculation: F [1], F [2]… f[27]

When we get to f[x], f[x-2], f[x-5], f[x-7], we’ve got the result

As shown in figure:

Figure 7 requires only one coin.

F [x] = the minimum number of coins to spell out x

F [x] = infinity means you can’t spell x with a coin

Reference code

public  static  int coinChange(int [] A, int M ) {
 int[] f = new int[M+1];
 int n = A.length;
 f[0] = 0;
 int i,j;
 for (i = 1; i<=M; i++) {
    f[i] = Integer.MAX_VALUE;
    for (j = 0; j< n; j++) {// Boundary condition judgment
        if(i >= A[j] && f[i - A[j]] ! = Integer.MAX_VALUE) { f[i] = Math.min(f[i - A[j]] +1, f[i]);
          // System.out.println(i + "=" +f[i]);}}}if (f[M] == Integer.MAX_VALUE) {
    f[M] = -1 ;
 }
 return  f[M];
}
@Test
public void isCoinChange(a) {
	int xx = {1.2.3};
    int b = 6;
    int i = coinChange(xx, b);
    Assert.assertNotNull(i);
}
Copy the code

😄


The core code is 4 Okay, that’s easy \color{red}{core code is only 4 lines, is very simple ~}

No.3

Leecode 62: different paths

A robot is located in the upper left corner of an m x N grid (the starting point is marked “Start” in the image below).

The robot can only move one step down or to the right at a time. The robot tries to reach the lower right corner of the grid (marked “Finish” in the image below).

How many different paths are there?

Look at the above problem solving steps, step by step

2.1. Dynamic programming Component 1: Determining status

The last step

No matter how the robot reaches the lower right corner, there is always a final move: – to the right or down

If shown, let’s set the lower right coordinate to be (m-1,n-1).

So the position of the robot before the last step is m minus 2,n minus 1, or m minus 1,n minus 2.

subproblems

So, if the robot has x ways to go from the top left corner to (m-2,n-1), and Y ways to go from the top left corner to (m-1,n-2), then the robot has x +Y ways to go to (m-1,n-1).

The question becomes, how many ways can the robot go from the top left corner to (m-2,n-1) or (m-1,m-2)?

If it goes to (m-2,n-1), as shown in the figure:

We can just kill the last column

Similarly, if you go to m minus 1,n minus 2 rows, you subtract one row.

Status:

Let f[I][j] be how many ways the robot can go from the top left corner to (I,j).

2.2. Dynamic programming Component 2: Transfer equations

For any lattice:

f[i][j] = f[i-1][j] + f[i][j-1]

1 2 3

1 represents how many ways the robot can go [I][J]

2 represents how many ways the robot can get to F [i-1][J]

3 is how many ways the robot can go to F [I][j-1]

2.3. Dynamic Programming Component 3: Initial and boundary conditions

Initial condition: F [0][0]=1, because the robot has only one way to get to the upper left corner

Boundary case: I =0 or j=0, then the previous step can only come in one direction, that is, row 0 or column 0. Each step has only one case, then f[I][j] = 1, and other regions satisfy the transition equation.

3.4. Dynamic programming Component 4: Computation order

Row by row. Why row by row?

F [0][1] and F [1][0] have already been calculated. Similarly, these two coordinates have also been calculated by column calculation. There is no need to calculate again.

  • f[0][0] = 1
  • Calculate line 0: f[0][0], F [0][1],… ,f[0][n-1]
  • Calculate line 1: F [1][0], F [1][1],… ,f[1][n-1]
  • .
  • Calculate line m-1: f[m-1][0], F [m-1][1],… ,f[m-1][n-1]

Time complexity: O(mn)

Reference code

public int uniquePaths(int m, int n) {
    int[][] f = new int[m][n];
    int i,j;
    for (i = 0; i<m; i++) {
        for (j = 0; j< n; j++) {
            if (i == 0 || j == 0) {
                f[i][j] = 1;
            } else {
                f[i][j] = f[i -1][j] + f[i][j-1]; }}}return f[m-1][n-1];
}

@Test
public void isUniquePaths(a) {
    int i = uniquePaths(3.3);
    Assert.assertNotNull(i);
}
Copy the code

Can see here friends, you have more than 80% of the people, may now your head began a little dizzy, brush questions is like this, brush a few will have a headache, rest, this fun son see is to insist.

To summarize

What problems can WE do with dynamic programming?

Counting 1.

  • How many ways to go to the bottom right
  • How many ways can I pick k numbers and the sum of yes is sum

2. Find the maximum and minimum values

  • The maximum number sum of paths from the top left to the bottom right
  • Longest ascending subsequence length

3. Existence

  • Take stone game, whether the first hand will win
  • Can you pick k numbers such that the sum is sum

Good luck! Let’s do the fourth problem.

No.4

Leecode 5. Longest callback substring

Given a string s, find the longest echo substring in s. You can assume that the maximum length of s is 1,000.

Example 1: Enter: “babad”

Output: “bab” Note: “ABA” is also a valid answer.

Example 2: Enter: “CBBD”

Output: “bb”

After reading the previous article, let’s go in four steps

1.1. Dynamic programming Component 1: Determining status

To put it simply, when solving dynamic programming, we need to open an array. What does each element of the array f[I] or f[I][j] stand for, similar to what does x, y, and z stand for in math

In this problem, we define f[I][j] to indicate whether the i-th through JTH characters of string s is a palindrome

Solving dynamic programming requires two consciences:

  • The last step
  • subproblems

The last step

Let’s use example 1 to explain, the figure below is the judgment process of step 1 and step 2, obviously the last step is the letter b with subscript 4 compared to all the previous elements, resulting in the longest echo substring.

subproblems

We can see that if f[I] =f[j], it is a palindrome

F [I]j] = f[I +1]f[j-1] : from I to j is a palindrome, so from I +1 to j-1 must also be a palindrome

So in the figure above we need to determine that a is equal to a

1.2. Dynamic Programming Component 2: Transfer equations

For a string of length from I to j, determine that it is a palindrome:

f[i]j] = f[i+1]f[j-1]

F [I +1][j-1] = f[I +2]f[j-2] = f[I +1]

1.3. Dynamic Programming Component 3: Initial and boundary conditions

If the number of residual determination letters is less than 3 and f[I] = f[j], it must be a palindrome.

For the letter itself, f[I][I], the string from I to I, it’s also a palindrome.

1.4. Dynamic programming Component 4: Computation sequence

In the figure above, we use j to match 0~ I (I < j).

It’s On^2 in time, and On^2 in space because it’s two-dimensional

Of course, there are other solutions such as center diffusion and horse-drawn carts.

Reference code

// Dynamic programming
public String longestPalindrome(String s) {
    / / sentence
    int len = s.length();
    if (len < 2) {
        return s;
    }

    int maxLen = 1;
    int begin = 0;

    // dp[I][j] indicates whether s[I, j] is a palindrome
    boolean[][] dp = new boolean[len][len];
    char[] charArray = s.toCharArray();

    for (int i = 0; i < len; i++) {
        dp[i][i] = true; // Palindrome
    }
    for (int j = 1; j < len; j++) {
        for (int i = 0; i < j; i++) {
            if(charArray[i] ! = charArray[j]) { dp[i][j] =false;
            } else {
                if (j - i < 3) {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = dp[i + 1][j - 1]; // In order to satisfy this condition, we must first satisfy j-i > 3}}// If dp[I][j] == true, the substring s[I..j] is palindrome
            if (dp[i][j] && j - i + 1 > maxLen) {
                maxLen = j - i + 1; begin = i; }}}return s.substring(begin, begin + maxLen);
}

@Test
public void islongestPalindrome(a) {
    String i = longestPalindrome("babaxaxab");
    Assert.assertNotNull(i);
}
Copy the code

Get ready for a very practical question 👍 👍 👍

No.5

Leecode 10. Match the regular expression

Given a string s and a character rule p, you are asked to implement a regular expression match that supports ‘.’ and ‘*’.

‘.’ matches any single character

‘*’ matches zero or more of the preceding elements

By matching, you want to cover the whole string S, not part of the string.

Example 1:

Input: s = “aab” p = “c * a * b” (* no space)

Output: true,

Explanation: Since ‘*’ means zero or more, here ‘c’ is zero and ‘a’ is repeated once. So it matches the string “aab”.

Example 2:

Input: s = “Mississippi” p = “misisp*.”

Output: false

Explanation: The second * does not match si

2.1. Dynamic programming Component 1: Determining status

Wc, how do you decide to use dynamic programming?

  • Look at the problem. You need to match it step by step
  • There’s no time or space complexity limit, you can choose >On
  • Similar to the previous problem, we need to consider the case of * and.
  • Try to write the transfer equation according to the steps

In this problem, we define f[I][j] to indicate whether the first I characters of string s match the first J characters of string p

Solving dynamic programming requires two consciences:

  • The last step
  • subproblems

The last step

For example: s = “aaab” p = “aa*b”

So we know that s has to be fully matched, so we just use s to match every character in p, so our last step is to match every character in p with the b character in s, and match whether the last character b is equal.

subproblems

There are several cases that need to be discussed, where s is used to match the last character j that p matches

  • F [I][j] = f[i-1][j-1]

  • If it is “.” To match any character at the end of s, only:

    f[i][j] = f[i-1][j-1]

  • If an asterisk (*) is used, zero characters or one or more characters are matched

    F [I][j] = f[I][j-2], because if j is *, we can match p j-1 any number of times, of course zero times is j-2.

If it matches 1 or more characters: F [I][j] = f[I -1][j] = f[I -1][j] = f[I -1][j] = f[I -1][j] = f[I -1][j] = f[I -1] = f[I -1] You can match it directly, and you can match it multiple times. (Multiple matches are based on the results of the previous match)

2.2. Dynamic programming Component 2: Transfer equations

Some of the cases that we analyze in the subproblem are the transfer equations

2.3. Dynamic Programming Component 3: Initial and boundary conditions

Because I minus one and J minus one, notice the boundary

boolean[][] f = new boolean[m + 1][n + 1];

f[0][0]=true

2.4. Dynamic programming Component 4: Computation sequence

S is used to match each character in the p string

Its time complexity is Onm, and its space complexity is Onm because it’s two-dimensional

Reference code

public boolean isMatch(String s, String p) {
    int m = s.length();
    int n = p.length();

    boolean[][] f = new boolean[m + 1][n + 1];
    f[0] [0] = true;
    for (int i = 0; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (p.charAt(j - 1) = =The '*') {
                f[i][j] = f[i][j - 2];
                if (matches(s, p, i, j - 1)) {
                    f[i][j] = f[i][j] || f[i - 1][j]; }}else {
                if (matches(s, p, i, j)) {
                    f[i][j] = f[i - 1][j - 1]; }}}}return f[m][n];
}

public boolean matches(String s, String p, int i, int j) {
    if (i == 0) {
        return false;
    }
    if (p.charAt(j - 1) = ='. ') {
        return true;
    }
    return s.charAt(i - 1) == p.charAt(j - 1);
}
@Test
public void isisMatch(a) {
     boolean i = isMatch("aa"."a*");
     Assert.assertNotNull(i);
}
Copy the code

No.6

Keep going, keep going ❤️❤️❤️❤️

Leecode 32. Longest valid parenthesis

Given a string containing only ‘(‘ and ‘)’, find the length of the longest valid (properly formed and continuous) parenthesis substring.

Example 1:

Input: s = “(()”

Output: 2

Explanation: The longest valid parenthesis substring is “()”

Example 2:

Input: s = “)()())”

Output: 4

Explanation: The longest valid parenthesis substring is “()()”

Example 3:

Input: s = “”

Output: 0

Tip:

0 <= s.length <= 3 * 104

S [I] = ‘(‘ or ‘)

After reading the previous article, let’s go in four steps

1.1. Dynamic programming Component 1: Determining status

To put it simply, when solving dynamic programming, we need to open an array. What does each element of the array f[I] or f[I][j] stand for, similar to what does x, y, and z stand for in math

Wc, how do you decide to use dynamic programming?

  • Look at the problem. You need to verify the maximum length step by step
  • There’s no time or space complexity limit, you can choose >=On
  • And very much like we did before, we need to think about generating parentheses.
  • Try to write the transfer equation according to the steps

In this problem, we define d[I] to be the length of the longest valid parenthesis ending with a subscript II character

Solving dynamic programming requires two consciences:

  • The last step
  • subproblems

The last step

Let’s use the figure below to explain, I as the last bracket judgment, we only make the judgment for the left bracket, the left bracket is divided into two cases, see the subproblem split.

subproblems

The first case is… (a)

Since the parentheses may be preceded by valid parentheses, we previously defined that d[I] represents the length of the longest valid parentheses at the end of the subscript I character, so we can derive:

d[i] = d[i-2] + 2

The second case is… )

In the figure, the subscript is 2: i-D [i-1] -1

There may be multiple valid parentheses before subscripts 2 and 5, but they are all d[i-1], because we define d[i-1] as the length of the longest valid parentheses at the end of the character of subscript i-1

The length of the longest valid parenthesis:

d[i] = x + y

X = d[I – d[I -1] -2

Here y = d[I -1] + 2

D [I] = D [I – D [I -1] -2] + d[I -1] + 2

1.2. Dynamic Programming Component 2: Transfer equations

D [I] indicates the length of the longest valid parenthesis ending with the subscript I character

d[i] = d[i – d[i-1] -2] + d[i-1] + 2

1.3. Dynamic Programming Component 3: Initial and boundary conditions

So just like in some of the previous problems, we need to determine the i-th character to determine the I-th character, so I starts at 1, and I minus 2 has to be considered out of bounds.

(1)… () : i >=2

(2)… I-d [i-1] = 0

1.4. Dynamic programming Component 4: Computation sequence

From left to right

It’s On in time and On in space

Of course, there are other solutions such as stacks

Reference code

public int longestValidParentheses(String s) {
    int maxans = 0;
    int[] dp = new int[s.length()];
    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] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
            }
            maxans = Math.max(maxans, dp[i]);
        }
    }
    return maxans;
}

@Test
public void isLongestValidParentheses() {
    String s = "()(())";
    longestValidParentheses(s);
}
Copy the code

No.7

This one is relatively simple – from the balding engineer 👥👥👥👥

Leecode 42. Catch rainwater

Given n non-negative integers representing the height diagram of each column of width 1, calculate how much rain can be received by the columns arranged in this order after it rains.

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]

Output: 6

Explanation: above is the height map represented by the array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water can be connected (the blue part represents rain water).

Example 2:

Input: height = [4,2,0,3,2,5]

Output: 9

Tip:

n == height.length

0 <= n <= 3 * 104

0 <= height[i] <= 105

After reading the previous article, let’s go in four steps

This is a little bit more difficult, because in a normal problem, we usually do it from left to right, or right to left, or top to bottom.

1.1. Dynamic programming Component 1: Determining status

To put it simply, when solving dynamic programming, we need to open an array. What does each element of the array f[I] or f[I][j] stand for, similar to what does x, y, and z stand for in math

Wc, how do you decide to use dynamic programming?

  • Look at the problem. You need to verify the maximum length step by step
  • There’s no time or space complexity limit, you can choose >=On
  • Just like in the previous problem, you need to consider that the highest height of each step is the lowest height, because it may form a low height
  • Try to write the transfer equation according to the steps

In this problem, we define d[I] to represent the most effective rainwater ending in the character I

Solving dynamic programming requires two consciences:

  • The last step
  • subproblems

The last step

We can reduce the complexity by using the filling method. Get rid of the lowlands.

Figure out the maximum height (depth) at each position from left to right

Look from right to left and find the maximum height at each position

Let’s see what happens when they overlap

So the minimum height at each location is the amount of water stored at each location.

subproblems

We store the maximum values for each position from left to right and right to left

From the overlapped figure, it can be seen that the minimum value of the last position is 2, minus the height, and the storage value is 0.

1.2. Dynamic Programming Component 2: Transfer equations

ans += Math.min(left_max[i], right_max[i]) – height[i];

1.3. Dynamic Programming Component 3: Initial and boundary conditions

1.4. Dynamic programming Component 4: Computation sequence

Left to right + right to left

It’s On in time and On in space

Of course, there are other solutions such as stacks

Reference code

public int trap(int[] height) {
    if (height == null || height.length == 0)
        return 0;
    int ans = 0;
    int size = height.length;
    int[] left_max = new int[size];
    int[] right_max = new int[size];
    left_max[0] = height[0];
    for (int i = 1; i < size; i++) {
        left_max[i] = Math.max(height[i], left_max[i - 1]);
    }
    right_max[size - 1] = height[size - 1];
    for (int i = size - 2; i >= 0; i--) {
        right_max[i] = Math.max(height[i], right_max[i + 1]);
    }
    for (int i = 1; i < size - 1; i++) {
        ans += Math.min(left_max[i], right_max[i]) - height[i];
    }
    return ans;
}

@Test
public void istrap(a) {
    int[] candidates = {2.0.6.1};
    int i = trap(candidates);
    Assert.assertNotNull(i);
}
Copy the code

No.8

B: ❤️❤️❤️❤️ C: ❤️❤️❤️❤️ D: ❤️❤️❤️❤️

Leecode 44. Wildcard match

Given a string (s) and a character pattern (p), implement a ‘? ‘and ‘*’ matches.

‘? ‘can match any single character.

‘*’ can match any string (including empty strings).

A match is made when the two strings match exactly.

Description:

S may be empty and contain only lowercase letters from A to z.

P may be empty and contain only lowercase letters from a to z, and characters? And *.

Example 1:

Input:

s = “aa”

p = “a”

Output: false

Explanation: “a” does not match the entire string “aa”.

Example 2:

Input:

s = “aa”

p = “*”

Output: true,

Explanation: ‘*’ can match any string.

Example 3:

Input:

s = “cb”

p = “? a”

Output: false

Explanation: ‘? ‘matches ‘c’, but the second ‘a’ does not match ‘b’.

Example 4:

Input:

s = “adceb”

p = “ab”

Output: true,

Explanation: The first ” matches the empty string, and the second ” matches the string ‘dce’.

Example 5:

Input:

s = “acdcb”

p = “a*c? b”

Output: false

After reading the previous article, let’s go in four steps

1.1. Dynamic programming Component 1: Determining status

To put it simply, when solving dynamic programming, we need to open an array. What does each element of the array f[I] or f[I][j] stand for, similar to what does x, y, and z stand for in math

Wc, how do you decide to use dynamic programming?

  • Look at the problem. You need to verify the maximum length step by step
  • There’s no time or space complexity limit, you can choose >=On
  • So similar to the previous problem, we have to think about * and *, right? In the case.
  • Try to write the transfer equation according to the steps

In this problem, we define f[I][j] to indicate whether the first I characters of string s match the first J characters of string p

Solving dynamic programming requires two consciences:

  • The last step
  • subproblems

The last step

For example: s = “aaab” p = “aa*b”

So we know that s and p have to match, so we’re going to use s to match every character in p, so our last step is to use b in s to match every character in p, to match whether the last character is b.

subproblems

This is a subproblem analysis of ‘Dynamic Programming Day Two-Regular expression matching’

There are several cases that need to be discussed, where s is used to match the last character j that p matches

  • F [I][j] = f[i-1][j-1]

  • If it is “.” To match any character at the end of s, only:

    f[i][j] = f[i-1][j-1]

  • If an asterisk (*) is used, zero characters or one or more characters are matched

    F [I][j] = f[I][j-2], because if j is *, we can match p j-1 any number of times, of course zero times is j-2.

    If it matches 1 or more characters: F [I][j] = f[I -1][j] = f[I -1][j] = f[I -1][j] = f[I -1][j] = f[I -1][j] = f[I -1] = f[I -1] You can match it directly, and you can match it multiple times. (Multiple matches are based on the results of the previous match)

This is basically the same problem

There are several cases that need to be discussed, where s is used to match the last character j that p matches

  • F [I][j] = f[i-1][j-1]

  • If it’s “? To match any character at the end of s, only:

    f[i][j] = f[i-1][j-1]

  • If “” is used, there are two cases, the first is not needed, the second is needed to use *

Example: s = “ABC” p = “a*”.

On a traversal of s series p series *, just meet the dp [I] [j] = dp [I] [1] at the moment I = 1, j = 2,

Dp [1] [2] = dp [1] [1] = true. — No need to use *

Dp [I][j] = f[i-1][j], because it can match any letter.

Dp [2], [2] = dp [1] [2] = true. — Need to use *

Dp [I][j] = f[i-1][j], because it can match any letter.

Dp [3], [2] = dp [2] [2] = true. — No need to use *

1.2. Dynamic Programming Component 2: Transfer equations

The transfer equation can be seen in the subproblem analysis

1.3. Dynamic Programming Component 3: Initial and boundary conditions

Because I minus one and J minus one, notice the boundary

boolean[][] f = new boolean[m + 1][n + 1];

f[0][0]=true

When f[0][j], check whether j is *, because * can match null string

1.4. Dynamic programming Component 4: Computation sequence

Match each character in the S string to each character in the P string

Its time complexity is Onm, and its space complexity is Onm

Reference code

public boolean isWildcardMatch(String s, String p) {
    int m = s.length();
    int n = p.length();
    boolean[][] dp = new boolean[m + 1][n + 1];
    dp[0] [0] = true;
    for (int i = 1; i <= n; ++i) {
        if (p.charAt(i - 1) = =The '*') {
            dp[0][i] = true;
        } else {
            break; }}for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (p.charAt(j - 1) = =The '*') {
                dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
            } else if (p.charAt(j - 1) = ='? ' || s.charAt(i - 1) == p.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1]; }}}return dp[m][n];
}

@Test
public void isisWildcardMatch(a) {
    boolean i = isWildcardMatch("123"."1 *");
    Assert.assertNotNull(i);
}
Copy the code

No.9

This one is easy, relax ~👍👍👍👍

63. Different paths II

A robot is located in the upper left corner of an m x N grid (the starting point is marked “Start” in the image below).

The robot can only move one step down or to the right at a time. The robot tries to reach the lower right corner of the grid (marked “Finish” in the image below).

Now consider an obstacle in the grid. So how many different paths are there going to be from top left to bottom right?

Obstacles and empty positions in the grid are represented by 1 and 0 respectively.

Example 1:

Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]

Output: 2

Explanation:

There is an obstacle right in the middle of the 3×3 grid.

There are two different paths from the top left to the bottom right:

\1. To the right -> to the right -> down -> down

\2. Down -> down -> Right -> right

Example 2:

Input: obstacleGrid = [[0,1],[0,0]]

Output: 1.

Tip:

m == obstacleGrid.length

n == obstacleGrid[i].length

1 <= m, n <= 100

ObstacleGrid [I][J] is 0 or 1

Subject to

—

How did I explain dynamic programming to my 5-year-old niece?

—

Path 1, roughly the same, but with an obstacle, and we’ll just make the judgment that there is no obstacle.

2.1. Dynamic programming Component 1: Determining status

The last step

No matter how the robot reaches the lower right corner, there is always a final move: – to the right or down

If shown, let’s set the lower right coordinate to be (m-1,n-1).

So the position of the robot before the last step is m minus 2,n minus 1, or m minus 1,n minus 2.

subproblems

So, if the robot has x ways to go from the top left corner to (m-2,n-1), and Y ways to go from the top left corner to (m-1,n-2), then the robot has x +Y ways to go to (m-1,n-1).

The question becomes, how many ways can the robot go from the top left corner to (m-2,n-1) or (m-1,m-2)?

If it goes to (m-2,n-1), as shown in the figure:

We can just kill the last column

Similarly, if you go to m minus 1,n minus 2 rows, you subtract one row.

Status:

Let f[I][j] be how many ways the robot can go from the top left corner to (I,j).

2.2. Dynamic programming Component 2: Transfer equations

For any lattice:

f[i][j] = f[i-1][j] + f[i][j-1]

1 2 3

1 represents how many ways the robot can go [I][J]

2 represents how many ways the robot can get to F [i-1][J]

3 is how many ways the robot can go to F [I][j-1]

2.3. Dynamic Programming Component 3: Initial and boundary conditions

Initial condition: F [0][0]=1, because the robot has only one way to get to the upper left corner

Boundary case: I =0 or j=0, then the previous step can only come in one direction, that is, row 0 or column 0. Each step has only one case, then f[I][j] = 1, and other regions satisfy the transition equation.

If an obstacle is encountered, f[I][J] = 0.

3.4. Dynamic programming Component 4: Computation order

Row by row. Why row by row?

F [0][1] and F [1][0] have already been calculated. Similarly, these two coordinates have also been calculated by column calculation. There is no need to calculate again.

  • F [0][0]= 1 if the first one is an obstacle F [0][0]=0
  • Calculate line 0: f[0][0], F [0][1],… ,f[0][n-1]
  • Calculate line 1: F [1][0], F [1][1],… ,f[1][n-1]
  • .
  • Calculate line m-1: f[m-1][0], F [m-1][1],… ,f[m-1][n-1]

Time complexity: O(mn)

Reference code

class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    if (obstacleGrid == null || obstacleGrid.length == 0) {
        return 0;
    }

    // Define the dp array and initialize row 1 and column 1.
    int m = obstacleGrid.length, n = obstacleGrid[0].length;
    int[][] dp = new int[m][n];
    for (int i = 0; i < m && obstacleGrid[i][0] = =0; i++) {
        dp[i][0] = 1;
    }
    for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
        dp[0][j] = 1;
    }

    / / based on state transition equation dp [I] [j] = dp [j] + [I - 1] dp [I] [1] for recurrence.
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (obstacleGrid[i][j] == 0) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; }}}return dp[m - 1][n - 1];
}
Copy the code

So the version of the scroll array, when we know the maximum number of paths at the current position, we’re going to find the maximum number of paths at the next position, we just need to know the left and the top, and the space complexity is o(m).

Reference code

  public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    int n = obstacleGrid.length, m = obstacleGrid[0].length;
    int[] f = new int[m];

    f[0] = obstacleGrid[0] [0] = =0 ? 1 : 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (obstacleGrid[i][j] == 1) {
                f[j] = 0;

            } else 
            if (j - 1> =0 && obstacleGrid[i][j - 1] = =0) {
                f[j] += f[j - 1]; }}}return f[m - 1];

}
Copy the code

No.10

See the last question of this share, can see here, all are talents. ❤ ️ ❤ ️ ❤ ️ ❤ ️

Come a relatively simple topic!!

Leecode 64. Minimum path sum

Given an m x n grid containing non-negative integers, find a path from the top left to the bottom right that minimizes the sum of numbers on the path.

Note: You can only move down or to the right one step at a time.

 

Example 1:

Input: the grid = [,3,1 [1],,5,1 [1], [4, 2, 1]] output: 7 explanation: because the path 1-3-1-1-1 the sum of the minimum. Example 2:

Grid = [[1,2,3],[4,5,6

Tip:

m == grid.length

n == grid[i].length

1 <= m, n <= 200

0 <= grid[i][j] <= 100

Look at the previous problem, think about it, here use dynamic programming to solve the problem, consider a few points:

  1. Boundary processing
  2. Middle path
  3. This is going to be M times N times so we’re going to compare each cell, so we’re going to take the smaller value

Dp said [I] [j] from the upper left corner to (I, j) (I, j) position of minimum path and the initial conditions: dp [0] [0] = grid [0] [0]

When I >0 j=0 dp[I][0]=dp[i-1][0] + grid[I][0]; / / the grid [I] [0] is finally the value of a grid when I = 0 j > 0 dp [0] [1] = dp [0] [1] + grid [0] [j]; When I j > > 0 0 dp [I – 1] [1] = min (dp [j], [I – 1] dp [I]] [j – 1) + grid [I] [j];

Reference code:

class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int rows = grid.length, columns = grid[0].length;
        int[][] dp = new int[rows][columns];
        dp[0] [0] = grid[0] [0];
        for (int i = 1; i < rows; i++) {
            dp[i][0] = dp[i - 1] [0] + grid[i][0];
        }
        for (int j = 1; j < columns; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < columns; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]; }}return dp[rows - 1][columns - 1]; }}Copy the code

This article is participating in the “Nuggets 2021 Spring Recruiting activity”, click to view the details of the activity juejin.cn/post/693605…

❤ ️ ❤ ️ ❤ ️ ❤ ️

Thank you very much talented people can see here, if this article is well written, feel something, please like 👍 please pay attention to ❤️ please share 👥 for warm men I really very useful!!

If there are any mistakes in this blog, please comment and comment. Thank you very much!

At the end of the article, I have compiled a recent interview data “Java Interview Customs Manual”, covering Java core technology, JVM, Java concurrency, SSM, microservices, database, data structure and so on. You can obtain it from GitHub github.com/Tingyu-Note… More to come.