<p>Given two strings s and t, return <i>the number of distinct</i> <b><i>subsequences</i></b><i> of </i>s<i> which equals </i>t.</p>

<p>The test cases are generated so that the answer fits on a 32-bit signed integer.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;rabbbit&quot;, t = &quot;rabbit&quot;
<strong>Output:</strong> 3
<strong>Explanation:</strong>
As shown below, there are 3 ways you can generate &quot;rabbit&quot; from s.
<code><strong><u>rabb</u></strong>b<strong><u>it</u></strong></code>
<code><strong><u>ra</u></strong>b<strong><u>bbit</u></strong></code>
<code><strong><u>rab</u></strong>b<strong><u>bit</u></strong></code>
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;babgbag&quot;, t = &quot;bag&quot;
<strong>Output:</strong> 5
<strong>Explanation:</strong>
As shown below, there are 5 ways you can generate &quot;bag&quot; from s.
<code><strong><u>ba</u></strong>b<u><strong>g</strong></u>bag</code>
<code><strong><u>ba</u></strong>bgba<strong><u>g</u></strong></code>
<code><u><strong>b</strong></u>abgb<strong><u>ag</u></strong></code>
<code>ba<u><strong>b</strong></u>gb<u><strong>ag</strong></u></code>
<code>babg<strong><u>bag</u></strong></code></pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length, t.length &lt;= 1000</code></li>
	<li><code>s</code> and <code>t</code> consist of English letters.</li>
</ul>

# babgbag, bag. b is located 0, 2, and 4 position.
# numDistinct(s[1:], t[1:]) + numDistinct(s[3:], t[1:]) + numDistinct(s[5:], t[1:])

# dp[i]: in i's position of t, we will have a list.
# for list's index represents the position of the i's position character in t for s.
# for list's value represents the number of combination.

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        if (len(s) < len(t)):
            return 0
        # from here, len(s) >= len(t)
        character_positions = []
        for ti in t:
            character_position = set()
            for index in range(len(s)):
                si = s[index]
                if (ti == si):
                    character_position.add(index)
            character_positions.append(character_position)
        
        # now we get character_positions. and let's initialize the first dp element.
        dp = [[0 for _ in range(len(s))] for _ in range(len(t))]
        character_position = character_positions[0]
        for i in character_position:
            dp[0][i] = 1

        # let's start dp
        for dp_index in range(len(t)-1):
            # let's update dp_index + 1 by using dp_index
            cur_pos = character_positions[dp_index + 1]
            for si in range(len(s)):
                if (si == 0):
                    continue
                dp[dp_index + 1][si] = dp[dp_index + 1][si - 1] + dp[dp_index][si-1]
            for si in range(len(s)):
                if (not(si in cur_pos)):
                    dp[dp_index+1][si] = 0
        # return answer
        output = 0
        cur_pos = character_positions[len(t)-1]
        for cur_po in cur_pos:
            output = output + dp[len(t)-1][cur_po]
        return output


120658