def solve(s, t):
    sl, tl = len(s), len(t)
    dp = [[0]*(sl+1) for _ in range(tl+1)]
    for w in range(sl+1):
        dp[0][w] = 1
    for h in range(1, tl+1):
        for w in range(1, sl+1):
            if s[w-1] == t[h-1]:
                dp[h][w] = dp[h-1][w-1] + dp[h][w-1]
            else:
                dp[h][w] = dp[h][w-1]
    return dp[-1][-1]

assert solve("rabbbit", "rabbit") == 3