很好的思路本题体面
小红拿到了一个仅由数字字符组成的字符串。她准备选择一个非空子序列,使得该子序列中不包含连续的”61”子串。
小红想知道,有多少种不同的子序列选择方式?答案对1e9+7mod
//这种以数字为结尾的我们在蓝桥杯的接龙中也出现了我们一般是进行转移表示在dp[i][j] 表示在i位置 以数字j结尾的状态是什么特征
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10,mod=1e9+7;
int dp[N][10];
int n;
int main ()
{
string s; cin>>s;
n=s.size(); s=' '+s;
for(int i=1;i<=n;i++)
{
dp[i][s[i]-'0']++;
for(int j=0;j<=9;j++)
{
dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;// 表示在继承上一个的答案也就是 answer // 1自己一个结尾
if(j==6&&s[i]=='1') continue;//表示在某种特殊要求之下要被舍去的答案
dp[i][s[i]-'0']=(dp[i-1][j]+dp[i][s[i]-'0'])%mod; // 表示在当前的时候寻找可以转移的方程
// 表示所有方案中可以满足的要求 也就是 //我自己结尾并且配上以前的所有的情况
}
}
int ans=0;
for(int i=0;i<=9;i++) ans=(ans+dp[n][i])%mod;
cout<<ans<<endl;
return 0;
}
// 表示是否选择以6 为结尾的数量转移
//不选也是方案数量
核心还是落在选与不选上面
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10,mod=1e9+7;
long long dp[N][2];
int n;
int main ()
{
string s; cin>>s;
n=s.size();
dp[0][0]=1;
for(int i=1;i<=n;i++)
{
if(s[i-1]=='6')
{
dp[i][0]=dp[i-1][0];
dp[i][1]=(dp[i-1][1]+dp[i-1][0]+dp[i-1][1])%mod;
}
else if(s[i-1]=='1')
{
dp[i][0]=(dp[i-1][0]+dp[i-1][0])%mod;
dp[i][1]=dp[i-1][1];
}
else
{
dp[i][0]=(dp[i-1][0]+dp[i-1][1]+dp[i-1][0])%mod;
dp[i][1]=dp[i-1][1];
}
}
int ans=(dp[n][1]+dp[n][0]-1+mod)%mod;
cout<<ans<<endl;
return 0;
}
tql