2019-08-08 吴亲库里 库里的深夜食堂
这道题有点意思的。给定两个字符串，要你在字符串S中找出所有字符串T的子序列。第一个b太多了，容易弄混，直接看例子2。最终的结果是5，就说明在babgbag中能找出5个bag这样的子序列。你可以中间删除或者不删,T是bag,从S的第一个字符串找，先ba,下一个是b,bab不是他的子序列，在下一个是g,现在S中babg删掉b就是子序列了。就是这样的顺序，可以从中删除掉不符合的字符，但是位置不能对换来比较，最终有五个组合。
不是很像爬楼梯的问题吗？就是在求字符串S长度为m时和字符串T长度为n时匹配情况，那么我们就需要求字符串S长度为[m-1]和字符串T长度为[n]-1的匹配情况....那么他的递推方程就是
$dp[$m][$n]=$dp[$m-1][$n]+$dp[$m-1][$n-1]||+0为什么有可能是加0呢。因为在匹配的过程中如果S[$m-1] !==$t[$n-1],就说明他的上一级S的第m-1和t的n-1位置是不匹配的,用上面的例子通俗的解释这句话就是在babg匹配bag的时候至少有bab匹配bag种情况。还有一点返回的可能会是0，这其实就是边界的问题，因为是在S中找等于T的子序，所以输入值的时候T可以是空值，空值是任意字符串的子序列，S和T也可以同时为空，但是S为空的时候，如果T不为空，那么一定是0。
/**
* @param String $s
* @param String $t
* @return Integer
*/
function numDistinct($s, $t) {
$m=strlen($s);
$n=strlen($t);
for($i=0;$i<$m;$i++) $dp[$i][0]=1;
for($i=1;$i<=$m;$i++){
for($j=1;$j<=$n;$j++){
if($s[$i-1]==$t[$j-1]){
$dp[$i][$j] =$dp[$i-1][$j]+$dp[$i-1][$j-1];
}else{
$dp[$i][$j]=$dp[$i-1][$j];
}
}
}
return $dp[$m][$n]??0;
}
