• leetCode 115.不同的子序列 动态规划 + 滚动数组（优化）

    给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 10^9 + 7 取模

    示例 1：

    输入：s = "rabbbit", t = "rabbit"
输出：3
解释：如下所示, 有 3 种可以从 s 中得到 rabbit" 的方案
rabbbit
rabbbit
rabbbit

     示例 2：

    输入：s = "babgbag", t = "bag"
输出：5
解释：如下所示, 有 5 种可以从 s 中得到 "bag" 的方案 
babgbag
babgbag
babgbag
babgbag
babgbag

    >>思路和分析

    下文参考(～￣(OO)￣)ブ笨猪爆破组的文章解法和文字：115. 不同的子序列 - 力扣（LeetCode）

    在s串身上“挑选”字符，去匹配 t串 的字符，求挑选的方式数

    （1）递归思路：抓住“选”，s 要按照 t 来挑选，逐字符考察“选”或“不选”，分别来到什么状态？

    • 1.s[i] == t[j]
      • 举例：s 为 babgbag,t 为 bag，末尾字符相同，故 s 有两种选择
      • 注意：int n = s.length(),m = t.length();
        • 1.用s[n-1] 去匹配掉 t[m-1]，问题规模缩小：继续考察 babgba 和 ba 
        • 2.若s[n-1] 不去匹配掉 t[m-1]，可由于t[m-1] 仍需被匹配，于是在 babgba 中继续挑，考察babgba 和 bag
      • 是否用s[n-1]去匹配t[m-1]，是两种不同的挑选方式，各自做下去所产生的方式数，相加起来，是大问题的解

    ​

    • 2.s[i] != t[j]
      • s[i] 不匹配 t[j]，唯有拿 s[i] 之前的子串去匹配

    （2）递归函数返回

    返回： 从开头到s[i]的子串中，出现『从开头到t[j]的子串』的次数。 即，从 前者 选字符，去匹配 后者 的方案数

    （3）递归树底部的base case

    一步步地递归压栈，子问题规模（子串长度）在变小：

    • 小到 t 变成空串，此时 s 去匹配它，方式只有一种：就是什么字符都不用挑（或 s 也是空串，啥也不用做也可匹配，方式数也是1）
    • 小到 s 变成空串，但t不是， s 是没有办法匹配 t 的，方式数为0

    递归函数的参数可以传子串或索引：这里推荐用索引描述子问题，因为不用每次都切割字符串，也更容易迁移到dp解法去

    一、递归搜索 (会超时)

    • 超出时间限制
    1. class Solution {
    2. public:
    3.     // 递归搜索 (会超时)
    4.     int numDistinct(string s,string t) {
    5.         const int n = s.length(),m = t.length();
    6.         function<int(int,int)> dfs = [&](int i,int j) -> int {
    7.             if(j<0) return 1;// base case
    8.             if(i<0) return 0;// 这两个base case 的顺序不能调换！因为 i<0 且 j<0 时 应该返回1
    9.             if(s[i] == t[j]) return dfs(i-1,j) + dfs(i-1,j-1);
    10.             else return dfs(i-1,j);
    11.         };
    12.         return dfs(n-1,m-1);
    13.     }
    14. };

    二、递归搜索 + 保存计算结果 = 记忆化搜索

    • 二维memo数组 存储计算过的子问题的结果 
    1. // 递归搜索 + 保存计算结果 = 记忆化搜索
    2.     int numDistinct(string s, string t) {
    3.         int n = s.length(),m = t.length(),memo[n][m]; // 二维memo数组 存储计算过的子问题的结果
    4.         memset(memo,-1,sizeof(memo));// -1 表示没有访问过
    5.         function<int(int,int)> dfs = [&](int i,int j) -> int { // 从开头到s[i]的子串中，出现『从开头到t[j]的子串』的 次数
    6.             if(j<0) // base case 当j指针越界，此时t为空串，s不管是不是空串，匹配方式数都是1
    7.                 return 1;
    8.             if(i<0) // base case i指针越界，此时s为空串，t不是，s怎么也匹配不了t，方式数0
    9.                 return 0;
    10.             if (memo[i][j] !=  -1) // memo中有当前遇到的子问题的解，直接拿来返回
    11.                 return memo[i][j];
    12.             if (s[i] == t[j]) {  // t[j]被匹配掉，对应dfs(i-1, j-1)，不被匹配掉对应dfs(i-1, j)
    13. 			    memo[i][j] = dfs(i-1, j) + dfs(i-1, j-1);
    14. 		    } else {
    15. 			    memo[i][j] = dfs(i-1, j);
    16. 		    }
    17.             return memo[i][j];// 返回当前递归子问题的解
    18.         };
    19.         return dfs(n-1,m-1);//从开头到s[n-1]的子串中，出现『从开头到t[m-1]的子串』的次数
    20.     }

    也可以写成这样的代码： 

    1. class Solution {
    2. public: 
    3.    // 递归搜索 + 保存计算结果 = 记忆化搜索
    4.     int numDistinct(string s, string t) {
    5.         int n = s.length(),m = t.length(),memo[n][m]; 
    6.         memset(memo,-1,sizeof(memo));
    7.         function<int(int,int)> dfs = [&](int i,int j) -> int { 
    8.             if(j<0) return 1;
    9.             if(i<0) return 0;
    10.             int &res = memo[i][j];
    11.             if (res !=  -1) return res;
    12.             if (s[i] == t[j]) return res = dfs(i-1, j) + dfs(i-1, j-1);
    13. 		    return res = dfs(i-1, j);
    14.         };
    15.         return dfs(n-1,m-1);
    16.     }
    17. };

    三、动态规划 与 递归 的区别 

    • 递归公式 
    1. if (s[i] == t[j]) { 
    2.     memo[i][j] = dfs(i-1, j) + dfs(i-1, j-1);
    3. } else {
    4.     memo[i][j] = dfs(i-1, j);
    5. }

    递归是自上而下调用，子问题自下而上被解决，最后解决了整个问题，而dp是从base case 出发，通过在dp数组记录中间结果，自下而上地顺序地解决子问题

    • dp解法

    1.确定dp数组（dp table）以及下标的含义

    dp[i][j]:从开头到s[i-1]的子串中，出现『从开头到t[j-1]的子串』的 次数。即：

    • 前 i 个字符的 s 子串中，出现前 j 个字符的 t 子串的次数
    • 或者说 以i-1为结尾的s子序列中出现以j-1为结尾的 t 的个数

    2.确定递推公式

    状态转移方程：

    • 当s[i-1] != t[j-1]时，有dp[i][j] = dp[i-1][j]
    • 当s[i-1] == t[j-1]时，有dp[i][j] = dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

    3.dp数组初始化

    base case

    • j==0时，dp[i][0] = 1
    • i==0时，dp[0][j] = 0

     

     也可从递推公式dp[i][j] = dp[i-1][j-1] + dp[i-1][j];和dp[i][j] = dp[i-1][j];中可以看出dp[i][j]是从上方和左方推导而来的，故：dp[i][0] 和 dp[0][j] 是一定要初始化的

    4.确定遍历顺序

    从递推公式我们可以看出dp[i][j]是从上方和左方推导而来的，所以遍历的时候一定是从上到下、从左到右，可以保证dp[i][j]可以根据之前计算出来的数值进行计算

    5.举例推导dp数组

    前言：看有些小伙伴，在不知道递推式的情况下，也能够手推递推式，引发了我的好奇心。于是我就开始了冥思苦想，究竟如何通过填表格就可以手推出呢？于是我开始反推，把dp数组打印出来，然后思考其表示的含义，接着在一步步地思考，知道了如何填表格的原理。

    提供另一种思路：以s："heeeheheda"，t："heheda"为例，推导dp数组状态如下（可以参考此图，可在不知道递推式的情况下找出规律，手推递推式），例如：

    "hee" 有 2 种组合可出现 "he"，也就是："hee"，"hee"

    "heeeheh" 有 8 种组合可以出现 "heh"，也就是："heeeheh","heeeheh","heeeheh","heeeheh","heeeheh","heeeheh","heeeheh","heeeheh"

    以此类推，我们就可以得到这样一个dp表格，尝试去看数据之间有没有什么内在联系，试着手推递推式，思路仅供参考 ！！！

    以s："heeeheheda"，t："heheda"为例，推导dp数组状态如下：

    可以发现，这里是把上面推出的表格，上外围多加了一层0，做外围多加了一层1，这样做的好处是可以统一操作，简化代码，也可以更加方便的利用滚动数组进行状态压缩

    和这篇文章的leetCode 718.最长重复子数组 动态规划 + 优化（滚动数组 的做法一样！！！！

    以s："babgbag"，t："bag"为例，推导dp数组状态如下：

    以s："rabbbit"，t："rabbit"为例，推导dp数组状态如下：

     （一）动态规划 二维dp

    1. for(int i=0;i<=n;i++) dp[i][0] = 1; 
    2.               ↓
    3. for(int i=0;i < n;i++) dp[i][0] = 1;

    注意：可以去掉一个=，是因为dp[n][1-m]可以由递推式推出，即左上方和上方的值推出，而dp[n][0]这个值用不到，所以可以省去这个初始化！

    至于第一行的初始化为0，数组一开始初始化为0了，所以这一步可以省略！

    for(int j=1;j0][j] = 0;
    1. class Solution {
    2. public:
    3.     // 动态规划 二维dp数组
    4.     int numDistinct(string s, string t) {
    5.         int n = s.length(),m = t.length();
    6.         uint64_t dp[n+1][m+1];
    7.         memset(dp,0,sizeof(dp));
    8.         for(int i=0;i0] = 1; 
    9.         // for(int j=1;j
    10.         for(int i=1;i<=n;i++) {
    11.             for(int j=1;j<=m;j++) {
    12.                 if(s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
    13.                 else dp[i][j] = dp[i-1][j];
    14.             }
    15.         }
    16.         return dp[n][m];
    17.     }
    18. };
    • 时间复杂度: O(n * m)
    • 空间复杂度: O(n * m)

     （二）动态规划 二维dp 优化空间复杂度

    1. class Solution {
    2. public:
    3.     // 动态规划 二维dp优化空间复杂度
    4.     int numDistinct(string s, string t) {
    5.         int n = s.length(),m = t.length();
    6.         uint64_t dp[2][m+1];
    7.         memset(dp,0,sizeof(dp));
    8.         for(int i=0;i<2;i++) dp[i][0] = 1;
    9.         for(int j=1;j0][j] = 0;
    10.         for(int i=1;i<=n;i++) {
    11.             for(int j=1;j<=m;j++) {
    12.                 if(s[i-1] == t[j-1]) dp[i%2][j] = dp[(i-1)%2][j-1] + dp[(i-1)%2][j];
    13.                 else dp[i%2][j] = dp[(i-1)%2][j];
    14.             }
    15.         }
    16.         return dp[n%2][m];
    17.     }
    18. }
    • 时间复杂度: O(n * m)
    • 空间复杂度: O(m)

     （三）动态规划 一维dp（滚动数组） 优化空间复杂度

    1. class Solution {
    2. public:
    3.     // 动态规划 一维dp 优化空间复杂度
    4.     int numDistinct(string s, string t) {
    5.         int n = s.length(),m = t.length();
    6.         uint64_t dp[m+1];
    7.         memset(dp,0,sizeof(dp));
    8.         dp[0] = 1;
    9.         for(int j=1;j0;
    10.         for(int i=1;i<=n;i++) {
    11.             // int pre = dp[0];
    12.             // for(int j=1;j<=m;j++) {
    13.                 // int tmp = dp[j];
    14.                 // if(s[i-1] == t[j-1]) dp[j] = pre + dp[j];
    15.                 // else dp[j] = dp[j];
    16.                 // pre = tmp;
    17.             // }
    18.             for(int j=m;j>=1;j--) {
    19.                 if(s[i-1] == t[j-1]) dp[j] = dp[j-1] + dp[j];
    20.             }
    21.         }
    22.         return dp[m];
    23.     }
    24. };
    1. 方法一
    2. // 顺序遍历的话，会覆盖上一层的dp数据，需要添加 pre变量 和 tmp变量 ，可以记录上一轮的dp数据
    3. int pre = dp[0];
    4. for(int j=1;j<=m;j++) {
    5.     int tmp = dp[j];
    6.     if(s[i-1] == t[j-1]) dp[j] = pre + dp[j];
    7.     else dp[j] = dp[j];
    8.     pre = tmp;
    9. }
    10.          ↓
    11.          ↓
    12.          ↓
    13. 方法二
    14. // 逆序遍历，就不会覆盖上一轮的dp数据，从而可以用dp[j-1]来代替pre
    15. for(int j=m;j>=1;j--) {
    16.     if(s[i-1] == t[j-1]) dp[j] = dp[j-1] + dp[j];
    17. }

    两种方法都可以跑得通，大家可以仔细对比一下他们之间的区别和好处！

    1. if(s[i-1] == t[j-1]) dp[j] = dp[j-1] + dp[j];
    2.                     ↓
    3. if(s[i-1] == t[j-1]) dp[j] += dp[j-1];

     进一步，可以写成这样，看起来简洁点！

    • 时间复杂度: O(n * m)
    • 空间复杂度: O(m)

    参考和推荐文章、视频：

    115. 不同的子序列 - 力扣（LeetCode）icon-default.png?t=N7T8https://leetcode.cn/problems/distinct-subsequences/solutions/661537/shou-hua-tu-jie-xiang-jie-liang-chong-ji-4r2y/

    代码随想录 (programmercarl.com)icon-default.png?t=N7T8https://programmercarl.com/0115.%E4%B8%8D%E5%90%8C%E7%9A%84%E5%AD%90%E5%BA%8F%E5%88%97.html#%E5%85%B6%E4%BB%96%E8%AF%AD%E8%A8%80%E7%89%88%E6%9C%AC

    动态规划之子序列，为了编辑距离做铺垫 | LeetCode：115.不同的子序列_哔哩哔哩_bilibiliicon-default.png?t=N7T8https://www.bilibili.com/video/BV1fG4y1m75Q/?spm_id_from=pageDriver&vd_source=a934d7fc6f47698a29dac90a922ba5a3

    来自代码随想录课堂截图：

  • 相关阅读:
    Java完全自学手册，从外包到大厂，再到年薪100万都靠它
    【Rust 日报】2022-10-28 GAT 要在 1.65 里稳定！
    如何使用SOLIDWORKS添加装饰螺纹线规格
    螺旋矩阵_数组 | leecode刷题笔记
    java自定义注解及其使用
    mini-centos7 环境安装部署，各种踩坑。。。
    Tensorrt自定义Plugin的调用顺序
    C和指针 第14章 预处理器 14.3 条件编译
    odoo16原码安装后，psycopg2模块出错，应用除了网站其它都安装不了
    Spring Boot 3.x Web MVC实战：实现流缓存的request
  • 原文地址：https://blog.csdn.net/weixin_41987016/article/details/133777587