本文转载自微信公众号「bigsai」，作者bigsai。转载本文请联系bigsai公众号。序言里，面试官笑着问了我一个问题，场景还原：然后我把这道题研究透了，由浅入深地分析了这道题的思路，分别有几拍和不同的子序列问题。有好几拍。这是拍拍的问题。分析如何找到字符串中有多少拍。不要想着三重for循环来枚举所有的情况，那不是一个好办法。如果你对这类题有灵感，应该能猜到这应该是一道动态规划题。首先简单分解一下问题，如果你问原字符串中有多少个p。然后再枚举就很容易了。例如，序列ppp是三个p。如果带a，字符串pa的个数是多少？pa由p和a组成。求出pa的个数肯定和a有很大的关系。根据这个a前面p的个数，每个a可以组成几个pa。只需添加由所有a位置组成的pa。例如，pppapa总共可以合并3+4=7pa。也很容易知道多少拍是理想的。求解pat需要找到每一个t，然后知道当前位置前面有多少个pas。将溶液叠加得到的结果是Can。最好结合下图看流程。不同的子序列题目描述：给定一个字符串s和一个字符串t，计算t在s的子序列中出现的次数。字符串的子序列是指在不干扰其余字符的相对位置的情况下，删除一些（或不删除）字符形成的新字符串。（例如，“ACE”是“ABCDE”的子序列，但“AEC”不是）问题数据保证答案在32位有符号整数的范围内。示例1：输入：s="rabbbit",t="rabbit"输出：3解释：如下图所示，有3种方法可以从s中获取“rabbit”。（上面的箭头符号^表示选中的字母）rabbbit^^^^^^rabbbit^^^^^^rabbbit^^^^^^例2：输入：s="babgbag",t="bag"输出：5解释：如下图所示，有5种方法可以从s中得到“bag”。（上面的箭头符号^表示选择的字母）ofEnglishletters作文分析：这道题其实就是上面几pat的变形和扩展。基本思路其实是一样的。上面的问题问的是pat有多少，是固定的，很短。但是t字符串的长度是不固定的，所以需要用数组来处理，不能直接ifelse。这道题的思路也一定是动态规划dp，dp[j]表示s中可以匹配到的t字符串中[0,j-1]长字符的个数（当然这个值是从前面动态变化的到后面），数组大小为dp[t.length+1]。在遍历s字符串的每一个元素时，都要和t字符串中的所有元素进行比较，看是否相等。如果s字符串枚举的字符串等于t字符串中的第j个。那么dp[j+1]+=dp[j]。你可能会问为什么是dp[j+1]，因为第一个元素需要匹配到数字+1，而这里为了避免（判断是否是第一个字符）这样的判断我们将dp[0]=1，所以t串的每个元素都可以正常操作。但是需要注意一点，在遍历s字符串中的第i个字母时，遍历t字符串一定不能是从左到右，而是从右到左。因为在枚举dp数组的时候遍历s字符串的第i个字符时，要求数据此刻是一个相对静态的叠加（即同级不能有影响），遇到相同的字符来自从左到右会对后面的数值产生影响。区别可以参考下图中的例子：实现代码为：classSolution{publicintnumDistinct(Strings,Stringt){chars1[]=s.toCharArray();chart1[]=t.toCharArray();intdp[]=newint[t1.length+1];dp[0]=1;//for(inti=0;i
