判断子序列
dp[i][j] 表示以下标i-1为结尾的字符串s,和以下标j-1为结尾的字符串t,相同子序列的长度为dp[i][j]。
if (s[i - 1] == t[j - 1])
t中找到了一个字符在s中也出现了
if (s[i - 1] != t[j - 1])
相当于t要删除元素,继续匹配
不同的子序列
dp[i][j]:以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。
s[i - 1] 与 t[j - 1]相等
s[i - 1] 与 t[j - 1] 不相等
当s[i - 1] 与 t[j - 1]相等时,dp[i][j]可以有两部分组成。
一部分是用s[i - 1]来匹配,那么个数为dp[i - 1][j - 1]。即不需要考虑当前s子串和t子串的最后一位字母,所以只需要 dp[i-1][j-1]。
一部分是不用s[i - 1]来匹配,个数为dp[i - 1][j]。
因为是在s里删元素找t的特征串而不是想法 所以不用考虑t[j - 1]
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
+左边是考虑使用当前元素 右边是不考虑使用当前元素
如:s:“bagg” t:“bag”
初始化
dp[i][0] = 1 如果t为空 那么就只能吧s全删了得到t 也就是只有一种方法
dp[0][j] = 0 这里不考虑t为空 那么在s为空的情况下 s无论如何也得不到t