leetcode算法笔记（offer收割机之不同的子序列）

导读：算法哥在前面的文章里分享了一系列的动态规划算法，相信坚持阅读下来的粉丝肯定收获满满，其实动态规划没什么高深的，见的多了，自然就容易想到！今天咱们再来一道hard模式的动态规划题吧！

给定一个字符串 S 和一个字符串 T，计算在 S 的子序列中 T 出现的个数。

一个字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

题目来源：LeetCode 115. Distinct Subsequences

示例 1:

示例 2:

这道题目初一读起来，感觉还挺拗口，其实想明白了非常简单！假设字符串s的长度是s_len，字符串t的长度是t_len，我们令dp[i][j]表示字符串s的前i个字符的子串里包含字符串t前j个字符的数量！那题目所要求的不就是求dp[s_len][t_len]！哈哈，得到这个玩意有啥用呢？还记得动态规划的核心思想吗，大问题转化成小问题，小问题推导大问题，现在我们要求dp[i][j]，那怎么求呢？我们先直接给出状态转移方程：

我们接下来分析一下这个递推式的思考过程：

情形1：

假设现在s[i]等于t[j]，那么dp[i][j]是不是就等于dp[i-1][j-1]，这个地方读者需要自己思考一下，其实很简单，想不明白就想想dp[i][j]代表的含义！

情形2：

假设现在字符串s的前i-1个字符的子串已经可以匹配字符串t的前j个字符，相当于把字符串s的第i个字符删了，也就是对应我们的dp[i-1][j]！

情形3：

那是不是还存在一个dp[i][j-1]呢？显然不存在，因为我们只能删除字符串s的字符，并不能添加字符串t的字符，dp[i][j-1]是推导不到dp[i][j]的！所以情形3不存在！

如果看完前面的分析过程，还有点模糊的，在仔细想想dp[i][j]代表的含义，多思考一下，一定能想明白！

我们上源码：

代码其实非常短小，只有区区15行，两个for循环，就把这个看似摸不着头脑的题目拿下了，其实，这里面还有一个地方，算法哥要提示下，源程序里，字符串的下标是从1算起的，这么做是方便写程序，因为不用判断i-1小于0了，还有dp[0][0]等于1，这个留给读者自己思考，为什么是等于1呢，为啥不等于0？

时间复杂度，两层for循环，显然是O(mn)的，m和n分别表示两个字符串的长度，空间复杂度，如果不做任何优化，也是O(mn)的，但是算法哥给的源码里，又使用了滚动数组的技巧，成功把空间复杂度降低到O(n)，这个技巧在算法哥的分享里，反复出现，粉丝们学会了吗？

这个题目，看似无从下手，其实透过现象看本质，题目并不难，要解决这个问题，需要突破以下几个难点：

1. 知道动态规划的核心思想，把大问题转化成小问题来解决；
2. 知道根据题目的要求，理清思路，找到正确的状态转移方程；
3. 编码的时候注意一些技巧，下标的选取，滚动数组的运用；

聪明的读者，题目又分享完了，麻烦动动手指送算法哥上头条吧，您的关注，点赞，评论，转发，都是对算法哥最大的鼓励！