Leetcode 115. different subsequences

Leetcode 115. Different subsequences
Topic linking
subject ： Given a string s And a string t , Calculated at s In the subsequence of t Number of occurrences .

One of the strings Subsequence Refer to , By deleting some （ It can also be done without deleting ） Character and does not interfere with the relative position of the remaining characters of the new string .（ for example ,“ACE” yes “ABCDE” A subsequence of , and “AEC” No ）

The data of the questions ensure that the answers are in line with 32 Bit signed integer range .

 Insert a code chip here 
 Input ：s = "rabbbit", t = "rabbit"
 Output ：3
 explain ：
 As shown in the figure below ,  Yes  3  Species can be obtained from  s  Get in  "rabbit"  The plan .
( Up arrow sign  ^  Indicates the selected letter )
rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^

The solution is on the official website , Here is just a record of personal problems

Q1: Why is it dp[0][0] Time is the answer ？
A1： There is a key sentence in the solution ：
Create a 2D array dp, among dp[i][j] It means that s[i:] In the subsequence of t[j:] Number of occurrences .
In the above expression ,s[i:] Express s From the subscript ii Substring to the end ,t[j:] Express t From the subscript j Substring to the end .
So when i=0,j=0 when , It means from s First character s[0] To end character s[m-1] In the subsequence of t[0] To t[n-1]（ String character t） Number of occurrences .

Q2： Why? s[i] And t[j] Consider two aspects when equal ？s[i]=t[j] But what does mismatch mean ？
A2： When equal , You need to judge each t Whether the characters in are equal to s The characters in , When there is no match ,dp[i][j] = dp[i+1][j] It means if it doesn't match ,t[j] remain unchanged , Move s[i], This is the same as that in the title Subsequence Refer to , By deleting some （ It can also be done without deleting ） Character and does not interfere with the relative position of the remaining characters of the new string . Corresponding .

Finally, you can write questions , Don't forget to turn up the array , Or you'll cross the line .

Not necessarily right , If there are mistakes, you are welcome to point them out ！