[Golang Theme Learning month] Over the weekend, I have done several dynamic programming questions and released a super exquisite teaching version, which has a very good response. Next, I will use two languages to brush the coding questions, respectively GO and JAVA.
Liver for many days – dynamic planning ten even – super delicate analysis | brush title punch card
What problem can I choose to do dynamic programming?
Counting 1.
- How many ways can I get to the bottom right corner
- How many ways can I pick the sum of k numbers yes is sum
2. Find the maximum and minimum
- The maximum numeric sum of the path from the upper left corner to the lower right corner
- Maximum ascending subsequence length
3. Seek existence
- Stone game, whether the first hand will win
- Can we pick k numbers such that the sum is sum
Leecode 115. Different subsequences
Given a string s and a string t, count the number of occurrences of t in a subsequence of S.
A subsequence of strings is a new string formed by deleting some (or none) characters without interfering with the relative positions of the remaining characters.
(For example, “ACE” is a subsequence of “ABCDE”, but “AEC” is not)
The question data ensures that the answers fit into the range of 32-bit signed integers.
Example 1:
Enter: s = “rabbbit”, t = “rabbit”
Output: 3
Explanation: As shown below, there are three ways to get “rabbit” from S.
(Top arrow symbol ^ indicates the selected letter)
rabbbit
^ ^ ^ ^ ^ ^
rabbbit
^ ^ ^ ^ ^ ^
rabbbit
^ ^ ^ ^ ^ ^
Example 2:
Enter: s = “babgbag”, t = “bag”
Output: 5
Explanation: As shown below, there are five ways to get “bag” from S. (Top arrow symbol ^ indicates the selected letter)
babgbag
^ ^ ^
babgbag
^ ^ ^
babgbag
^ ^ ^
babgbag
^ ^ ^
babgbag
^ ^ ^Copy the code
Tip:
0 <= S. length, t.length <= 1000 s and T consist of letters
—
Four steps for dynamic planning ~~~ ❤️❤️❤️❤️
2.1. Dynamic planning component 1: State determination
To put it simply, when solving dynamic programming, you need to open an array. What does each element of the array f[I] or f[I][j] represent, similar to what x, y, and z represent in mathematical problems
The last step
If the s string is a subsequence of the T string, we directly compare whether the last letter is equal (because when both s and T have only one letter, they are the last letter)
For example: s = “babgbag”, t = “bag”
If the length of the s string is less than the length of the t string, it returns 0, no subsequence.
subproblems
Subproblem analysis, we determine if the last letter matches, so there are two cases
— If the last letter matches:
Can be deduced: dp [I] [j] = dp + 1] [I [j + 1) + dp [j], [I + 1] see j I + 1 + 1 is a subsequence, here with dp + 1] [I [j] because, for example: S =babc, t= BC, when the second b of the s string matches the first b of the T string, it needs to add the previously unmatched subsequence.
— If the last letter does not match:
It can be deduced that dp[I][j]=dp[I +1][j] to see if j is a subsequence of I +1, e.g. S = bac,t = BC
Nice \color{yellow}{very nice ~} very nice ❤️❤️❤️
2.2. Dynamic programming component 2: Transfer equation
We looked at the subproblem analysis, which is essentially the analysis of these two cases.
The transfer equation is easy to write:
dp[i][j]=dp[i+1][j+1]+dp[i+1][j]
dp[i][j]=dp[i+1][j]
2.3. Dynamic programming component 3: Initial conditions and boundary cases
The string length of s >= the string length of t
If t is empty, then empty can be a subsequence of S.
2.4. Dynamic programming component 4: Order of calculation
Top down or bottom up
Reference code
The language version
func numDistinct(s, t string) int {
m, n := len(s), len(t)
if m < n {
return 0
}
dp := make([] []int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
dp[i][n] = 1 // // For t, if t is null, null is a subsequence of the S string, so null is a subsequence group of each character of S
}
for i := m - 1; i >= 0; i-- {
for j := n - 1; j >= 0; j-- {
if s[i] == t[j] {
dp[i][j] = dp[i+1][j+1] + dp[i+1][j]
} else {
dp[i][j] = dp[i+1][j]
}
}
}
return dp[0] [0]}Copy the codeJAVA version
public int numDistinct(String s, String t) {
int m = s.length(), n = t.length();
if (m < n) {
return 0;
}
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
dp[i][n] = 1; // For t, if t is null, null is a subsequence of the s string, so null is a subsequence combination of each character of S.
}
for (int i = m - 1; i >= 0; i--) {
char sChar = s.charAt(i);
for (int j = n - 1; j >= 0; j--) {
char tChar = t.charAt(j);
if (sChar == tChar) {
dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j];
} else {
dp[i][j] = dp[i + 1][j]; }}}return dp[0] [0];
}
@Test
public void isnumDistinct(a) {
int i = numDistinct("babc"."bc");
Assert.assertNotNull(i);
}
Copy the code❤ ️ ❤ ️ ❤ ️ ❤ ️
Thank you very much talent can see here, if this article is written well, feel that there is something to ask for praise 👍 for attention ❤️ for share 👥 for handsome Oba I really very useful!!
If there are any mistakes in this blog, please comment, thank you very much!
At the end of this article, I recently compiled an interview material “Java Interview Process Manual”, covering Java core technology, JVM, Java concurrency, SSM, microservices, databases, data structures and so on. How to obtain: GitHub github.com/Tingyu-Note… , more attention to the public number: Ting rain notes, one after another.