思路1 dp

注意这题cpp vector元素是int的话会溢出

dp[i][j] 表示 s中前i个和t中前j个字符 的不同子序列

• case1. s[i - 1] != t[j - 1]，则dp[i][j] = dp[i-1][j]。即s和t中最新的两个字符不同，所以不同子序列的个数和dp[i-1][j]是一样的

• case2. s[i - 1] == t[j - 1]，则dp[i][j] = dp[i-1][j] + dp[i - 1][j - 1]。即s和t中最新两个字符是相同的，则分成两种情况，（不包括s[i-1]和包括s[i-1]两种情况）

  s[0...i-2]中t[0...j-1]的数量 + s[0...i-1]中t[0...j-1]的数量

两个边界情况

• t是空串，空串是任意字符串的子序列，且不同子序列个数就是1，即dp[i][0] = 1

• s是空串，t.size >= 1，则为0，即dp[0][j] = 0, j >= 1

为啥状态方程是： s[i] == t[j] 时 dp[i][j] = dp[i-1][j-1] + dp[i-1][j] s[i] != t[j] 时 dp[i][j] = dp[i-1][j]

先看s[i] == t[j] 时，以s = "rara" t = "ra" 为例，当i = 3, j = 1时，s[i] == t[j]。 此时分为2中情况，用最后一位的a + 不用最后一位的a。 如果用s串最后一位的a,那么t串最后一位的a也被消耗掉（可以理解为被匹配掉了），此时的子序列其实=dp[i-1][j-1] 如果不用s串最后一位的a，那就得看"rar"里面是否有"ra"子序列的了，就是dp[i-1][j] 所以 dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

再看s[i] != t[j] 比如 s = "rarb" t = "ra" 还是当i = 3, j = 1时，s[i] != t[j] 此时显然最后的b想用也用不上啊。所以只能指望前面的"rar"里面是否有能匹配"ra"的 所以此时dp[i][j] = dp[i-1][j]