Understand Dynamic Programming through Leetcode 115 — explanation with pictures
Although question 115 is a ‘hard’ problem on Leetcode, but it is quite simple if you know how to use dynamic programming to solve problems.
Original question could be found HERE on Leetcode
Problem: 115. Distinct Subsequences (Hard)
📑Description:
Given a string S and a string T, count the number of distinct subsequences of S which equals T.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
Example 1:
Input: S = "rabbbit", T = "rabbit"
Output: 3
Explanation:As shown below, there are 3 ways you can generate "rabbit" from S.
(The caret symbol ^ means the chosen letters)rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^
Example 2:
Input: S = "babgbag", T = "bag"
Output: 5
Explanation:As shown below, there are 5 ways you can generate "bag" from S.
(The caret symbol ^ means the chosen letters)babgbag
^^ ^
babgbag
^^ ^
babgbag
^ ^^
babgbag
^ ^^
babgbag
^^^
📝Let’s show you the code first:
To understand how these code work, you can draw a table on the paper first, like this:
I use s = “rabbbit” and t = “rabbit” as an example:
You have to add an extra column and an extra row at the beginning of the table, because the whole precess should be initialized from an empty string (''). While you are coding on the computer, this table will be generated by the following code:
dp = [[0] * (len(s) + 1) for _ in range(len(t) + 1)]+1 is the first column and row in the table above
Than, fill the first row with number ‘1’
That means, strings in rabbbit:'', r, ra, rab, rabb, rabbb, rabbbi, rabbbit both include one '' inside it.
and then move to the next row, that means to inspect how many r in '', r, ra, rab, rabb, rabbb, rabbbi, rabbbit
What you will get is:
for r in string t, it cannot be included in the first element, which is '' in string s. so dp[1][0] must be 0
For the third row, it is the same
String ra cannot be included in string r, so dp[2][1] must be 0
For the fourth row, dp[3][4] should be 2 because there are two rab inside the substring of rabb
Now, the most difficult part to understand this matrix comes:
Why dp[4][5] is generated by the sum of dp[4][4] and dp[3][4]?
You can think like that:
dp[3][4] is the way to select the first ‘b’ from ‘bb’ to combind with the third b to form ‘bb’
dp[4][5] is the way to select two ‘b’ s from ‘bb’ and doesn’t care about the third b
If you understand that, the following step is quite simple, just copy the steps above, the final matrix looks like this:
Return the last element and that’s it