# Leetcode 115 - Distinct subsequences

Note

• dp[i][j] means the number of distinct sub between s[0 - i-1] that ends with s[i-1] and t[0 - j-1] that ends with t[j-1].
• When s[i-1] === t[j-1], two situations to consider:
• consider s[0 - i-2] and t[0 - j-2].
• Don’t consider s[i-1], take s[0 - i-2] and t[0 - j-1] into consideration.
• To initialize:
• dp[0][j] = 0 because t can’t be subsequence of an empty string.
• dp[i][0] = 1 because empty string is a subsequence of any string.

Given two strings s and t, return the number of distinct subsequences of s which equals t.

A string’s subsequence is a new string formed from the original string by deleting some (can be none) of the characters without disturbing the remaining characters’ relative positions. (i.e., “ACE” is a subsequence of “ABCDE” while “AEC” is not).

It is guaranteed the answer fits on a 32-bit signed integer.

Example