矩阵动态规划-子序列个数

给你两个字符串S和 T ，统计并返回在S 的 子序列 中T 出现的个数。

如果字符串S是”APAPT”， T字符串是”PAT”，哪到T出现的次数是1，”APAPT“
如果字符串S是”APAPTT”， T字符串是”PAT”，哪到T出现的次数是2，”APAPTT”， “APAPTT“
如果字符串S是”APAATT”， T字符串是”PAT”，哪到T出现的次数是4，”APAATT”，”APAATT“，”APAATT”，”APAATT“

如果字符串S是”APPAATTAPPAPATT”，PAT的出现次数是多少？

如果是用暴力搜索，S的长度n, T的长度是m, 时间复杂度接近O(n^m)，肯定不可取。

我们设nP, nPA, nPAT分别表示P、PA、PAT的出现次数，初始值为0；

int nP=0, nPA=0, nPAT=0;
string S="APPAATTAPPAPATT", T="PAT";
int n=S.length();
for(int i=0;i<n;i++){
    if(s[i]='P') nP+=1;
    if(s[i]='A') nPA+=nP;
    if(s[i]='T') nPAT+=nPA; 
}
cout<<nPAT;

实现代码：子序列不能有重复

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2024-12-26 18:48:45
 * 最后修改: 2024-12-26 19:56:52
 * 文件描述: 子序列的数量 (子序列没有重复值)
****************************************************************/

#include <iostream>
#include <vector>
using namespace std;

// 函数功能：计算字符串 s2 在字符串 s1 中作为子序列出现的次数（子序列没有重复值）
int countSubsequences(string s1, string s2) {
    int m = s2.size(), n = s1.size();
    int k; // 用于记录匹配到 s2 的索引
    vector<int> nums(m, 0); // nums[i] 表示 s2 的前 i+1 个字符作为子序列出现的次数
    
    // 遍历字符串 s1
    for (int i = 0; i < n; i++) {
        k = -1; // 初始化 k 为 -1，表示当前字符未匹配到 s2 中的任何字符
        
        // 在 s2 中查找当前字符 s1[i] 的位置
        for (int j = 0; j < m; j++) {
            if (s1[i] == s2[j]) {
                k = j; // 找到匹配位置
                break; // 退出内层循环
            }   
        }
        
        // 如果当前字符在 s2 中不存在，跳过
        if (k == -1) continue;
        
        // 如果匹配到 s2 的第一个字符
        if (k == 0)
            nums[k] += 1; // 第一个字符的子序列数量加 1
        else
            nums[k] += nums[k - 1]; // 其他字符的子序列数量由前一个状态累加
    }
    
    return nums.back(); // 返回 nums 数组的最后一个元素，表示完整的 s2 在 s1 中作为子序列的数量
}

int main() {
    // 输入两个字符串
    string s1;
    string s2;
    cin >> s1 >> s2;

    // 输出子序列的数量
    cout << "子序列的个数为: " << countSubsequences(s1, s2) << endl;
    return 0;
}

上面的方法无法处理子序列有重复值的情况，在上面思想拓展，用动态规划的方法实现，可以处理有重复值情况。

  for (int i = 2; i <= m; ++i) { // 选择 s2 前 i 个字符
        for (int j = i; j <= n; ++j) { // 选择 s1 前 j 个字符，必须有 j ≥ i
            if (s2[i] == s1[j]) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1]; // 如果对应字符相等，添加上上一状态的次数
            } else {
                dp[i][j] = dp[i][j - 1]; // 如果对应字符不等，继续使用上一种状态
            }
        }
    }

S=”RABBBIT”, T=”RABBT”

代码实现：时间复杂度是(m*n)

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2024-12-26 12:43:57
 * 最后修改: 2024-12-26 14:15:52
 * 文件描述: 求子序列的个数
****************************************************************/
#include <iostream>
#include <vector>
using namespace std;

// 函数功能：计算 s2 在 s1 中作为子序列出现的次数
int countSubsequences(string s1, string s2) {
    int m = s2.size(), n = s1.size();
    // dp[i][j] 表示 s2 前 i 个字符在 s1 前 j 个字符中作为子序列出现的次数
    vector<vector<int> > dp(m + 1, vector<int>(n + 1, 0));
    
    // 初始化：处理子序列 s2 只有一个字符的情况
    for(int i = 1; i <= n; i++) {
        if(s2[1] == s1[i]) 
            dp[1][i] = dp[1][i-1] + 1; // 如果 s2 的第一个字符与 s1 对应，添加一种新子序列
        else 
            dp[1][i] = dp[1][i-1]; // 否则，继续存在之前的次数
    } 
   
    // 状态转移：处理更长的子序列
    for (int i = 2; i <= m; ++i) { // 选择 s2 前 i 个字符
        for (int j = i; j <= n; ++j) { // 选择 s1 前 j 个字符，必须有 j ≥ i
            if (s2[i] == s1[j]) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1]; // 如果对应字符相等，添加上上一状态的次数
            } else {
                dp[i][j] = dp[i][j - 1]; // 如果对应字符不等，继续使用上一种状态
            }
        }
    }
    
    return dp[m][n]; // 返回最终结果：整个 s1 中包含整个 s2 的次数
}

int main() {
    // 输入两个字符串：s1 和 s2
    string s1;
    string s2;
    cin >> s1 >> s2;

    // 在字符串前面添加一个空格，便于进行 1-based 处理
    s1 = ' ' + s1;
    s2 = ' ' + s2;

    // 调用函数，计算子序列的次数
    cout << "子序列的个数为: " << countSubsequences(s1, s2) << endl;
    return 0;
}

优化（空间复杂度）

由于状态转移方程仅依赖上一行和当前行，因此可以将 dp 数组优化为一维数组。

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2024-12-26 12:43:57
 * 最后修改: 2024-12-26 22:36:39
 * 文件描述: 求子序列的个数
****************************************************************/
#include <iostream>
#include <vector>
using namespace std;

// 函数功能：计算 s2 在 s1 中作为子序列出现的次数
int countSubsequences(string s1, string s2) {
    int m = s2.size(), n = s1.size();
    // dp[i][j] 表示 s2 前 i 个字符在 s1 前 j 个字符中作为子序列出现的次数
    vector<int > dp(m + 1, 0);
    dp[0] = 1; // 空字符串是任何字符串的子序列
    
    // 状态转移：处理更长的子序列
    for (int j = 1; j <= n; ++j) { // 遍历 s1 的每个字符
        for (int i = m; i >= 1; --i) { // 从后往前遍历 s2，避免覆盖之前的状态
            if (s1[j] == s2[i]) {
                dp[i] += dp[i - 1]; // 如果匹配，将上一个状态的值累加到当前状态
            }
        }
    }

    return dp[m]; // 返回最终结果：整个 s1 中包含整个 s2 的次数
}

int main() {
    // 输入两个字符串：s1 和 s2
    string s1;
    string s2;
    cin >> s1 >> s2;

    // 在字符串前面添加一个空格，便于进行 1-based 处理
    s1 = ' ' + s1;
    s2 = ' ' + s2;

    // 调用函数，计算子序列的次数
    cout << "子序列的个数为: " << countSubsequences(s1, s2) << endl;
    return 0;
}

Previous Topic

Back to Lesson

Next Topic

数据结构与算法

矩阵动态规划-子序列个数

优化（空间复杂度）