dp（九）不同的子序列

不同的子序列_牛客题霸_牛客网【牛客题霸】收集各企业高频校招笔面试题目配有官方题解在线进行百度阿里腾讯网易等互联网名企笔试面试模拟考试练习,和牛人一起讨论经典试题,全面提升你的技术能力https://www.nowcoder.com/practice/ed2923e49d3d495f8321aa46ade9f873

描述

给定两个字符串S和T返回S子序列等于T的不同子序列个数有多少个

字符串的子序列是由原来的字符串删除一些字符也可以不删除在不改变相对位置的情况下的剩余字符例如"ACE"is a subsequence of"ABCDE"但是"AEC"不是
例如

S="nowcccoder", T = "nowccoder"

返回3

示例1

输入

"nowcccoder","nowccoder"

返回值

3

 题目意思就是在S串中找子串根T串相同呗说的绕的半天没搞懂题目意思搞懂题目意思之后就清晰了这种一般一维的肯定做不了直接定义二维状态一个i访问S串一个j访问T串

Fij表示 S串中的前i个字符在T串中前j个字符找到

在状态转移方程推导时自己一遍画表格一边推导当S[i] != T[j]时直接为上方之前的结果

当俩个元素相等的时候对照上图中2的位置它的上方1 与斜上方1然后考虑要不要删除S[i]对应字符如果不删除就使用上方之前的结果如果使用S当前这第二个c字符那就要抛弃第一个c在组成now的情况下使用第二个c来组成nowc把这俩种情况求和就是S串中的前i个字符在T串中前j个字符的不同序列个数

【解法一】

class Solution {
public:
    int numDistinct(string S, string T) {
        // write code here
        int row = S.size();
        int col = T.size();
        vector<vector<int>> dp(row+1, vector<int> (col+1));
        dp[0][0] = 1;
        for(int i = 1; i <= row; i++)
        {
            dp[i][0] = 1;
            for(int j = 1; j <= col; j++)
            {
                if(S[i-1] == T[j-1])
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
                else
                    dp[i][j] = dp[i-1][j];
            }
        }
        return dp[row][col];
    }
};

【解法二】滚动数组优化

class Solution {
public:
    int numDistinct(string S, string T) {
        int row = S.size();
        int col = T.size();
        vector<int> dp(col+1);
        dp[0] = 1;
        for(int i = 1; i <= row; i++)
            for(int j = col; j >= 1; j--)
                if(S[i-1] == T[j-1])
                    dp[j] += dp[j-1];
        return dp[col];
    }
};