2023年11月1日 - 动态规划15

392. 判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

dp[i][j]表示以i-1为结尾的字符串s和以j-1为结尾的字符串t的相同子序列的长度

 class Solution {
 public:
     bool isSubsequence(string s, string t) {
         vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));
         for (int i = 1; i <= s.size(); i++) {
             for (int j = 1; j <= t.size(); j++) {
                 if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                 else dp[i][j] = dp[i][j - 1];
             }
         }
         if (dp[s.size()][t.size()] == s.size()) return true;
         return false;
     }
 };

115. 不同的子序列

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

dp[i][j] 以i - 1 为结尾的s中有以j - 1为结尾的t个数

 class Solution {
 public:
     int numDistinct(string s, string t) {
         vector<vector<uint64_t>> dp(s.size() + 1, vector<uint64_t>(t.size() + 1));
         for (int i = 0; i < s.size(); i++) dp[i][0] = 1;
         for (int j = 1; j < t.size(); j++) dp[0][j] = 0;
         for (int i = 1; i <= s.size(); i++) {
             for (int j = 1; j <= t.size(); j++) {
                 if (s[i - 1] == t[j - 1]) {
                     dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; //当s中字符和t中字符相同时，要考虑是否使用s最后一个元素，dp[i - 1][j - 1]代表使用s最后一个元素，dp[i - 1][j]表示不使用s最后一个元素
                 } else {
                     dp[i][j] = dp[i - 1][j];
                 }
             }
         }
         return dp[s.size()][t.size()];
     }
 };