本人是个刚接触算法题的小白，写这篇文章是因为题解中的大佬写的文章对于刚接触
算法的小白来说有点晦涩难懂，我在最开始看这道题的时候看了好久大佬的题解才慢慢
理解了大佬的思路（😂），为了帮助更多和我一样的小白更好的理解这些题的解题思路
写了这篇文章，后面的内容如有错误还望多多包涵，接下来就让我们来看看这道题吧。

首先题目中的子序列并不是连续的子序列，中间是可以有跳跃的。
例如字符串“134”，它的子串就有{1,3,4,13,14（这个子串就是不连续的，中间跳过了一个3），134}，
然后我们设an为长度是n的字符串的子串数量，为了方便理解，下面我举几个例子；
例：字符串“3”，长度n=1，a1=1；
       字符串“32”，长度n=2，a2=3；
       字符串“321”，长度你=3，a3=7；
可以看出an=an-1*2+1；
原理就是“32”的子串有{3,2,32}；
在增加了一位变成”321“后，子串变成了
{3,2,32,31,21,321,1}
不知道大家注意到没有，加粗下划线的字体其实就是在前一个子串集合里的元素后面加上后加入的字符“1”，斜体下划线的字体就是最后加上个新增加的字符“1”；
上面的例子主要是为了让大家能更好的理解长度为n的字符串与长度为n+1的字符串之间子串的关系，
其实长度为n+1的字符串它的子串就是包括了长度为n的字符串的子串，并在n的每个子串后面加上一个
多出来的字符，再加上多出来的字符本身，那么子串对3求余的关系就如下面的例子
例：
     字符串“123”，子串{1,2,3,12,13,23,123}
     对3求余为0的子串：3,12,123；（数量为3）
     对3求余为1的子串：1,13；（数量为2）
     对3求余为2的子串：2,23；（数量为2）

     然后在字符串“123”的基础上加一个字符，这个要根据这个字符对3求余的不同情况进行分别讨论，
     例1：”1234“（加入了新字符“4”，对3求余余1）
     对3求余为0的子串：3,12,123,24,234；（数量为3+2（这个2是上面对3求余为2的子串加上新字符“4”后形成的新子串，因为之前的子串余2，加上新字符对3求余余1，余下的2+1等于3，刚好又对3求余时余0，下面的子串也同理））
     对3求余为1的子串：1,13，34,124,1234,4（数量为2+3+1（3的来源可以参考上面2的来源，这里就不细讲了，1的来源就是新加入的字符“4”））
    对3求余为2的子串：2,23,14,134（数量为2+2）

设bn，c为前n位字符对3求余余c的子串数量，
则可以总结出当新字符对3取余余1时
bn，0=bn-1，0  +  bn-1，2
bn，1=bn-1，1 + bn-1,0  + 1
bn,2=bn-1, 2 +bn-1,1
剩下的几种情况我就不再这里推导了，大家可以试着自己思考一下。
接下来就是动态规划的内容了，设置一个数组来存储计算过程中的数据date【50】【3】
date【50】【3】就是上面的例子bn，c
从第一个字符开始，计算对应求余子串并记录，然后读入字符串的下一位再用对应的公式对每一步
的计算结果进行存储与调用就可以计算出答案了，记得对结果取1e9+7余
下面附上我的代码，本人才开始接触这类算法题，有什么不足的地方望大佬指出， 
#include<iostream>
#include<cstring>
//此题的子串并非连续子串，中间可有间隔；
//还有对中间的计算过程的数字对N求余，不然数据中间可能会超，导致答案出错
const int N = 1e9 + 7;
using namespace std;
int main()
{
    string a;
    cin >> a;
    int lenth = a.size(), m = 0;long long date[50][3] = { 0 };
    m = (a[0] - '0') % 3;
    date[0][m] = 1;
    for (int i = 1;i < lenth;i++)
    {
        m = (a[i] - '0') % 3;
        switch (m)
        {
        //新字符余0的情况
        case 0:
        {
            date[i][0] = (date[i - 1][0] * 2 + 1) % N;
            date[i][1] = (date[i - 1][1] * 2) % N;
            date[i][2] = (date[i - 1][2] * 2) % N;
            break;
        }
        //新字符余1的情况
        case 1:
        {
            date[i][0] = (date[i - 1][0] + date[i - 1][2]) % N;
            date[i][1] = (date[i - 1][1] + date[i - 1][0] + 1) % N;
            date[i][2] = (date[i - 1][2] + date[i - 1][1]) % N;
            break;
        }
        //新字符余2的情况
        case 2:
        {
            date[i][0] = (date[i - 1][0] + date[i - 1][1]) % N;
            date[i][1] = (date[i - 1][1] + date[i - 1][2]) % N;
            date[i][2] = (date[i - 1][2] + date[i - 1][0] + 1) % N;
            break;
        }
        }
    }
    cout << date[lenth - 1][0] % N;//输出时取余，按照题目要求
    return 0;
}