C语言重构【115】不同的子序列

淩亂°似流年 2022-12-21 10:50 125阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
    
    字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"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" 的方案。 
    (上箭头符号 ^ 表示选取的字母)
    babgbag
    ^^ ^
    babgbag
    ^^    ^
    babgbag
    ^    ^^
    babgbag
      ^  ^^
    babgbag
        ^^^
     
    
    提示：
    
    0 <= s.length, t.length <= 1000
    s 和 t 由英文字母组成

#### 方案： ####

*  二维动态规划

class Solution
    { 
    public:
        int numDistinct(string s, string t)
        { 
            int slen = s.size();
            int tlen = t.size();
            vector<vector<long>> dp(tlen + 1, vector<long>(slen + 1, 0));
    
            for (int i = 0; i < slen; i++)
            { 
                dp[0][i] = 1;
            }
            for (int i = 0; i < slen; i++)
            { 
                for (int j = 0; j < tlen; j++)
                { 
                    if (s[i] == t[j])
                        dp[j + 1][i + 1] = dp[j][i] + dp[j + 1][i];
                    else
                        dp[j + 1][i + 1] = dp[j + 1][i];
                }
            }
            return dp[tlen][slen];
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(nm)
 *  空间复杂度：O(nm)

[Git]: https://github.com/ch98road/leetcode