判断字符串s中有多少个子序列和t相等

一个字符串的子序列是将字符串中若干字符删除后形成的字符串。

令dp[i][j]表示字符串s[0 : i-1]中和t[0 : j-1]相等的子序列个数，最终要求解的是dp[n][m]

假设字符串t为空，即m为0，那么dp[i][0]都应该为1，因为只需要将s中所有字符都删掉即可

求dp[i][j]的方法是

如果s[i - 1] == t[j - 1]，说明当前位置匹配，那么dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]，表示可以认为当前位置匹配计算个数和，也可以不认为当前位置匹配而在s前面寻找匹配位置
如果s[i - 1] != t[j - 1]，那么就老老实实的dp[i][j] = dp[i - 1][j]从s前面寻找匹配位置

int numDistinct(string s, string t) {
    vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));
    /* 最重要的是这里，所有迭代的动态规划最不好理解的也都是对dp设置初值
     * 由于本题只要t为空，那么可以将s中所有字符删掉就获得t，所以为1 */
    for(int i = 0; i <= s.size(); ++i)
        dp[i][0] = 1;
    for(int i = 1; i <= s.size(); ++i)
    {
        for(int j = 1; j <= t.size(); ++j)
        {
            /* 根据是否相等执行不同操作，因为此时需要匹配t[0 : j]，而只有相等时才可以允许只匹配t[0 : j-1] */
            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()];
}

子序列个数

对于一个序列a=a[1],a[2],......a[n]。则非空序列a'=a[p1],a[p2]......a[pm]为a的一个子序列，其中1<=p1<p2<.....<pm<=n。

输入：
第1行：一个数N，表示序列的长度(1 <= N <= 100000)
第2 - N + 1行：序列中的元素(1 <= a[i] <= 100000)

输出：假设不会溢出

dp[i] 表示考虑到第i位的所有可能数.

如果a[i] 是第一次被使用那么,dp[i] = dp[i - 1] * 2 + 1. 因为前面的可以取可以不取.

前面不取的话,就是a[i]一个数字。
如果前面取的话,那么a[i] 取不取则有dp[i - 1] * 2种。

如果a[i] 之前已经出现过了。比如 x1 x2 x3 1111 x4 x5 1212 那么 x1 x2 1111 和与 x1 x2 1212应该是同一种。所以需要减去以1111 为结尾的可能情况,就是dp[prePos]。而且那个+1也要去掉，因为dp[prePos]里面包含过a[i]一个数字的情况了。

#include <iostream>
#include <cstring>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
using namespace std;

int n; 
const int maxn = 1000010;
const int mod = 1e9 + 7;
int a[maxn];
int pos[maxn];
long long dp[maxn];
int main() {
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++) {
        scanf("%d",&a[i]);
    }

    for(int i = 1;i <= n;i ++) {
        if(pos[a[i]] == 0) {
            dp[i] = (dp[i - 1] * 2 + 1) % mod;
        }
        else {
            dp[i] = (dp[i - 1] * 2 - dp[pos[a[i]] - 1] + mod) % mod;
        }
        pos[a[i]] = i;
    }
    cout << dp[n] << endl;

}

最后编辑于：2020.06.17 09:42:52