字元串dp（easy）

被3整除的子序列

連結：https://ac.nowcoder.com/acm/problem/21302

來源：牛客網

題目描述

給你一個長度為50的數字串,問你有多少個子序列構成的數字可以被3整除

答案對1e9+7取模

輸入描述:

輸入一個字元串，由數字構成，長度小于等于50

輸出描述:

輸出一個整數

基本思路

除三取餘隻能得到0，1，2；

那就從頭開始周遊序列，依次求出除三取餘的餘數，用dp更新結果三種情況分别是

餘數=0

dp[0]=dp[0]+dp[0]+1;

dp[1]=dp[1]+dp[1];

dp[2]=dp[2]+dp[2];

餘數=1

dp[0]=dp[0]+dp[2];

dp[1]=dp[1]+dp[0]+1;

dp[2]=dp[2]+d[1];

餘數=2

dp[0]=dp[0]+dp[1];

dp[1]=dp[1]+dp[2];

dp[2]=dp[2]+dp[0]+1;

如果直接這樣寫會取用更新的最新值，是以用幾個變量存一下。

#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<string>
#include<set>
#include<vector>
using namespace std;
#define ll long long

/*ll qpow(ll a,ll b){
      ll ans=1;
	  while(b){
	  	if(b&1){
	  		ans=ans*a;
		  }
		  a=a*a;
		  b>>=1;
	  }
	  return ans;

}*/

/*const char *a[]={"ling","yi","er","san","si","wu","liu","qi","ba","jiu"};
struct s{
	string sfz;
	int sj,ks;
};*/
//int cmp(s a,s b){
//	return a.pj>b.pj;
//}
/*ll gcd(ll a,ll b) // 求最大公因數
{
    return b==0?a:gcd(b,a%b);
}

ll  lcm(ll a,ll b)
{
    ll k;
    k=a*b/(gcd(a,b));
    return k;
}*/
const int mod=1e9+7;
ll dp[1000008];
int main(){
	string s;
	cin>>s;
	ll m;
	ll m0,m1,m2;
	memset(dp,0,sizeof(dp));
	ll w=s.length();
	
	for(int i=0;i<w;i++){
		m=(s[i]-'0')%3;
		
		dp[m]=dp[m]%mod;
		m0=m1=m2=0;
		if(m==0){
			m0+=dp[0]+1;
			m1+=dp[1];
			m2+=dp[2];
		}
		else if(m==1){
			m0+=dp[2];
			m1+=dp[0]+1;
			m2+=dp[1];
		}
		else if(m==2){
			m0+=dp[1];
			m1+=dp[2];
			m2+=dp[0]+1;
		}
		dp[0]+=m0;
		dp[1]+=m1;
		dp[2]+=m2;
		for(int x=0;x<=2;x++){
			dp[x]=dp[x]%mod;
		}
	}
	cout<<dp[0];
	
} 
           

用二維dp可以用數組下标記錄更加友善

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
const int mod=1e9+7;
int main(){
    ll n,m,k,l,w,y;
    char s[55];
    int dp[55][4];
    memset(dp,0,sizeof(dp));
    scanf("%s",s+1);
    l=strlen(s+1);
    dp[1][(s[1]-'0')%3]=1;
    for(int i=2;i<=l;i++){
    m=(s[i]-'0')%3;
    dp[i][m]+=1;
    dp[i][m]%=mod;
    for(int j=0;j<3;j++){
        dp[i][j]+=(dp[i-1][j]+dp[i-1][(j+3-m)%3])%mod;
    }
    }
    cout<<dp[l][0]<<endl;
    }
           

String Game（吉林省賽）

Clair and Bob play a game. Clair writes a string of lowercase characters, in which Bob sets the puzzle

by selecting one of his favorite subsequence as the key word of the game. But Bob was so stupid that he

might get some letters wrong.

Now Clair wants to know whether Bob’s string is a subsequence of Clair’s string and how many times

does Bob’s string appear as a subsequence in Clair’s string. As the answer may be very large, you should

output the answer modulo 109 + 7.

Input

The first line is Clair’s string (whose length is no more than 5000), and the second line is Bob’s string

(whose length is no more than 1000).

Output

Output one line, including a single integer representing how many times Bob’s string appears as a

subsequence in Clair’s string. The answer should modulo 109 + 7.

題意就是給兩個字元串，求第二個字元串在第一個中出現過幾次

思路

從前往後周遊clair的字元串

從後往前周遊bob的字元串

dp[i]代表clair前i個字元有dp[j]種子序列等于bob前j個字元

#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<string>
#include<set>
#include<vector>
using namespace std;
#define ll long long
const int mod=1e9+7;
/*ll qpow(ll a,ll b){
      ll ans=1;
	  while(b){
	  	if(b&1){
	  		ans=ans*a;
		  }
		  a=a*a;
		  b>>=1;
	  }
	  return ans;
 
}*/
 
/*const char *a[]={"ling","yi","er","san","si","wu","liu","qi","ba","jiu"};
struct s{
	string sfz;
	int sj,ks;
};*/
//int cmp(s a,s b){
//	return a.pj>b.pj;
//}
/*ll gcd(ll a,ll b) // 求最大公因數
{
    return b==0?a:gcd(b,a%b);
}
 
ll  lcm(ll a,ll b)
{
    ll k;
    k=a*b/(gcd(a,b));
    return k;
}*/
 
ll dp[100008];
int main(){
	string s1,s2;
	while(cin>>s1){
		cin>>s2;
		memset(dp,0,sizeof(dp));
		for(int i=0;i<s1.size();i++){
			for(int j=s2.size()-1;j>=0;j--){
				if(s1[i]==s2[j]){
					if(j==0) dp[j]++;
				else {
					dp[j]+=dp[j-1];//s1第i位作為s2的第j位時，前j-1個字元的選擇有dp[j-1]種方法
					dp[j]=dp[j]%mod;
					
				}}
			}
		}
		cout<<dp[s2.size()-1]<<endl;//s2的長度為下标的dp值即為出現次數
 	}
}