LeetCode #115:Distinct Subsequences(不同的子序列)

题目描述

状态定义:dp[i][j] 为 s 的子串 s[0…i] 的子序列中,出现 t 的子串 t[0…j] 的数目。用一种更好理解的话来表述,即删去 s[0…i] 中若干个元素得到 t[0…j],有多少种不同的删法。

dp[i][j] 在任何时候都可以由 dp[i-1][j] 转移而来,因为本问题可以看作 “s 串中删去若干个元素得到串 t 有几种不同的删法”,可以理解为必定删除 s 串中索引为 i 的元素的情况,把问题转化为删去 s[0…i-1] 中若干个元素得到 t[0…j]。

额外地,当 s[i] == t[j] 时,dp[i][j] 还能从 dp[i-1][j-1] 转移而来,即不删除 s 串中索引为 i 的元素(因为 s[i] == t[j],末尾已经匹配了),把问题转化为删去 s[0…i-1] 中若干个元素得到 t[0…j-1]。

当 s[i] == t[j] 时,既可以删除 s 串中索引为 i 的元素来尝试匹配 t,也可以不删除(因为 s 和 t 末尾一致,只需要尝试匹配两串除末尾的部分即可)。

dp 数组初始化方面,我们需要先初始化二维 dp 数组的第 0 行和第 0 列,这样从行列下标 1 开始遍历数组。dp[0][0] 应看 s[0] 是否等于 t[0],等于赋值 1,否则赋 0。除去 dp[0][0] 的第 0 行元素 dp[0][j] 应该都为 0,因为若 s 比 t 要短无论如何也无法满足题意;除去 dp[0][0] 的第 0 列元素 dp[i][0],初始化为 t[0] 在串 s[0…i] 的出现次数。

代码实现如下:

class Solution {
public:
    int numDistinct(string s, string t) {
        int n = s.length();
        int m = t.length();

        vector<vector<unsigned long long>> dp(n, vector<unsigned long long>(m, 0));
        dp[0][0] = s[0] == t[0] ? 1 : 0; // 初始化dp[0][0]
        for(int i = 1; i < n; i ++) { // 初始化第0列,第0行已经在dp数组创建时置0
            if(s[i] == t[0]) {
                dp[i][0] = dp[i - 1][0] + 1;
            } else {
                dp[i][0] = dp[i - 1][0];
            }
        }

        for(int i = 1; i < n; i ++) {
            for(int j = 1; j < m; j ++) {
                if(s[i] == t[j]) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; // s[i]==t[j]时dp[i][j]有两种可能的转移来源
                } else {
                    dp[i][j] = dp[i - 1][j]; // s[i]!=t[j]时只有一种转移来源
                }
            }
        }

        return dp[n - 1][m - 1];
    }
};

发表回复

您的电子邮箱地址不会被公开。