跳到主要内容

LeetCode 115. 不同的子序列

本节目标

用倒序一维计数统计从源串中选取目标串的不同子序列方案数。

这是序列与字符串动态规划中一维倒序计数的拓展母题。

题意与约束​

统计从源串 s 删除若干字符后得到目标串 t 的不同方式数；保留的字符相对顺序不能改变。

第一反应与重复子问题​

处理一个源字符时，若它等于目标前缀的新末尾，可以选择它来延长所有匹配更短目标前缀的方案，也可以不选它。

状态定义与转移推导​

令 dp[j] 为已处理源串前缀匹配 t 前 j 个字符的方案数。dp[0]=1；当源字符等于 t[j-1] 时，dp[j]+=dp[j-1]，并从后向前更新。

正确性依据​

新增方案与旧方案按是否使用当前源字符互斥。倒序确保 dp[j-1] 仍来自处理当前字符之前的前缀，因此一个字符最多被选一次。

样例执行过程​

rabbbit 匹配 rabbit 时，三个 b 中选两个的不同位置组合形成 3 种方案。

代码实现​

C++17
#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    int numDistinct(string s, string t) {
        vector<unsigned long long> count(t.size() + 1, 0);
        count[0] = 1;
        for (char source : s) {
            for (int target = static_cast<int>(t.size()); target >= 1; target--) {
                if (source == t[target - 1]) {
                    count[target] += count[target - 1];
                }
            }
        }
        return static_cast<int>(count[t.size()]);
    }
};

复杂度分析​

设长度为 m,n，时间 O(mn)，一维状态空间 O(n)；C++ 中间计数使用 unsigned long long。

边界与易错点​

  • 源串短于目标串时答案为零。
  • 必须倒序更新；正序会让一个源字符在同轮重复贡献。

模式迁移​

组合计数、0/1 背包和匹配方案数都要先判断一维压缩后的依赖是否要求倒序。