【C++编程能力提升】

一、392 判断子序列

题目链接：392 判断子序列

核心：dp[i][j]表示以i-1结尾的s和以j-1结尾的j的数组构成公共子序列的长度，dp[i][j]值的确定有两种情况：其一当前元素的前一个元素对应相同，则说明可以构成公共子序列，其二是当前元素的前一个元素不相同，说明要比较i-1和j-2元素是否相同。
最后如果遍历到数组结束时公共子序列长度与s长度相同，说明s是t的子序列。

    bool isSubsequence(string s, string t) {
 //动态规划，设计二维dp数组，dp[i][j]表示以i-1结尾和j-1结尾的数组的公共子序列长度
    int len1=s.size();
    int len2=t.size();
    vector<vector<int>> dp(len1+1,vector<int>(len2+1,0));
    for(int i=1;i<=len1;++i)
    {
        for(int j=1;j<=len2;++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]; //不相同则比较i-1与j-2元素，即dp[i][j-1]
        }
    }
    if(dp[len1][len2]==s.size())
        return true;
    return false;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

二、115 不同的子序列

题目链接：115 不同的子序列

核心：dp[i][j]表示以i-1结尾的s和以j-1结尾的t的不同子序列数
dp[i][j]值的确定有两种情况，其一当前元素的前一个元素对应相同，那么dp[i][j]可以是用s[i-1]来匹配（dp[i-1][j-1]），也可以是不用s[i-1]来匹配（dp[i-1][j]）；其二是当前元素的前一个元素不相同时，dp[i][j]不用s[i-1]匹配。
此外dp[i][0]和dp[0][j]以及dp[0][0]的初始化是不同的。

    int numDistinct(string s, string t) {
    //动态规划:dp[i][j]以i-1结尾的s和以j-1结尾的t的不同子序列个数
    vector<vector<uint64_t>> dp(s.size()+1,vector<uint64_t>(t.size()+1));
//初始化，dp[i][0]和dp[0][j]的初始化不同，前者是s得到空串的个数是1，后者是空串得到t的个数是0
    for(int i=0;i<=s.size();++i)
        dp[i][0]=1;
    for(int j=1;j<=t.size();++j)
        dp[0][j]=0; //包括dp[0][0]=1
    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];
            else
                dp[i][j]=dp[i-1][j]; 
        }
    }
    return dp[s.size()][t.size()];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20