【Day3 中高难度算法挑战】不同的子序列
介绍
总而言之是时候利用暑假锻炼一下算法技术，一提算法面试就面露难色的情形总不能一直持续下去。本栏目面向有一定基础的编程爱好者，每天（如果up不鸽）分享并解析一道LeetCode中高难度题目（通常是hard）。有兴趣的小伙伴可以一起跟着做并且讨论解法。目前的教材是花花酱的Leetcode Problem List【1】.
适合人群：
有一定算法基础，但是还未能顺利通过笔试/面试，总觉得算法题目想不明白的你。
不适合人群：
算法入门级选手（一上来就做难题可能并不合适，建议首先专注简单/中等题目）
非常不适合人群：
算法竞赛选手（这种小儿科的问题完全是在浪费您的时间）
过往题目在这里！
不同的子序列
题目看这里，leetcode第一百一十五题，hard难度：
https://leetcode.com/problems/distinct-subsequences/
强烈建议读者自己先做（不过真的会有读者吗，笑），有任何问题欢迎在评论区讨论，up看到了会及时回复。做完了欢迎在评论区打卡～
解析
我们正在比较字符串s和t的各个字母。如果我们正在考虑的两个字母相同，那么我们有两种选择：
我们可以选择匹配这两个字母。看看如果我们移除当前匹配的字母，剩下的子串中有多少种方式可以形成相等的子序列。
我们也可以选择跳过s中的这个字母，只使用s前面的部分继续与t匹配。
但如果我们正在考虑的两个字母不相同，那么我们没有选择，我们只能跳过s中的这个字母，继续用s前面的部分去与t匹配。
思考乐园
上面的解释说：“我们也可以选择跳过s中的这个字母，只使用s前面的部分继续与t匹配”。那么为什么我们不能选择跳过t的这个字母，使用t前面的部分与s匹配呢？欢迎把答案写在评论区。
今天也同样送给大家一首好听的歌曲，那就是，来自MC石头的——情债！
教材链接
【1】https://zxi.mytechroad.com/blog/leetcode-problem-categories/
