dp练习

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+7;
const int mod = 1e9+7;
char s[100];
int n,dp[100][5],ans=0,a[500],x;
int main(){
　　cin>>s;
　　n=strlen(s);
　　for(int i=1;i<=n;++i)
　　a[i]=s[i-1]-'0';
　　dp[1][a[1]%3]++;
　　for(int i=2;i<=n;++i){
　　　　x=a[i]%3;
　　　　dp[i][x]=(dp[i][x]+1)%mod;
　　　　for(int j=0;j<=2;++j){
　　　　　　dp[i][j]=(dp[i][j]+dp[i-1][j]+dp[i-1][(j+3-x)%3])%mod;
　　　　　　　　//前i个中符合条件的个数
　　　　　　　　//当前位自身贡献+1
　　　　　　　　//前i个中余j的个数等于前i-1个中余j的个数加上
　　　　　　　　//前i-1个中余下 (j+3-x)%3的个数（因为当前计算上当前的x了
　　　　　　}
　　　　}
　　cout<<dp[n][0]<<endl;
　　return 0;
}