思路整理

我们可以看到的是，题目需要我们计算出子序列构成的数字是3的倍数的方案数。
首先需要找到最优子结构，dp[i][j]表示字符串s[i]结尾的数字中余数为j的方案数。
所以可以得到转移方程

#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
int dp[110][110];
int main()
{
 string s;
 cin >> s;
 int n = s.size();
 for (int i = 0; i < n; i ++) dp[i][(s[i] - '0') % 3] = 1;
 
 for (int i = 0; i < n; i ++) {
     for (int k = i + 1; k < n; k ++) {
         for (int j = 0; j < 3; j ++)
             dp[k][(s[k]+j-'0')%3] = (dp[k][(s[k]+j-'0')%3] + dp[i][j]) % mod;
     }
 }
 
 int res = 0;
 for (int i = 0; i < n; i ++)
     res = (dp[i][0] + res) % mod;
 cout << res << endl;
}