Distinct Subsequences Python Solution

lcpy gen -n 115   # by problem number
lcpy gen -s distinct_subsequences   # by problem name

Input: s = "rabbbit", t = "rabbit"
Output: 3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from s.
rabbbit
rabbbit
rabbbit

Input: s = "babgbag", t = "bag"
Output: 5
Explanation:
As shown below, there are 5 ways you can generate "bag" from s.
babgbag
babgbag
babgbag
babgbag
babgbag

class Solution:
    # Time: O(m * n)
    # Space: O(n) using a single rolling row
    def num_distinct(self, s: str, t: str) -> int:
        m, n = len(s), len(t)
        # dp[j] = number of ways to form t[:j] from the s prefix seen so far
        dp = [0] * (n + 1)
        dp[0] = 1  # empty t matches any s prefix exactly once
        for i in range(1, m + 1):
            # Iterate j backwards so dp[j-1] is still from the previous row
            for j in range(n, 0, -1):
                if s[i - 1] == t[j - 1]:
                    dp[j] += dp[j - 1]
        return dp[n]