动态规划

1. 动态规划的问题。想了好久终明白了，先写下来自己看了别人后的理解，免得以后又忘记了。
2. 思路：整体的思路就是，把输入的数字按顺序放到一个数组里面，然后每次依次加入一个数字。举一个例子，512。

   1、这时数组arr中的数据为5、1、2。然后进行循环。先进行第一次循环，先处理数字5。因为5对3取模的结果为2，所以dp[1][2]加一（即在只有5的情况下，对3取模只能得到余数为2的一个结果）。
   2、接下来再对第一层进行处理，因为第0层都是零，所以第一层的值不变。
   3、接下来开始操作第二个数，1对3取模是1，所以先让dp[2][1]=1，这一步其实就是看这一个数字单独的时候对3取模。然后循环操作这一层，因为1对3取模剩下一个1，与之前剩下2的那些数字结合正好能够满足拼成一个3，所以dp[2][0]=dp[2][0]+dp[1][0]+dp[1][2],dp[2][1]=dp[2][1]+dp[1][1]+dp[1][0],dp[2][2]=dp[2][2]+dp[1][2]+dp[1][1]。这一步的操作其实就是这个数字单独和之前对3取模剩下相应数字的和，然后加上能够与当前数字对3取模的和正好构成3的之前的数字的和。
   4、之后的步骤类似与第三步。

import java.util.*;

public class Solution {
    /*这里先定义好求余数的值。
    static int mod = 1000000000 + 7;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String data = in.next();
        char[] arr = data.toCharArray();
        int len = data.length();

        /*这里定义出一个长度为输入的数字位数加一，且每一层有三个位置的二维数组。
        int[][] dp = new int[len + 1][3];
        for (int i = 1; i <= len; i++) {

            /*这里先看看当前这个数字对3取模得到几。然后把相应的位置上加一
            int m = (arr[i - 1] - '0') % 3;
            dp[i][m] += 1;

            /*这里是一次操作这个数字加上之后余数分别为0、1、2的个数。
            for (int j = 0; j < 3; j++) {
                dp[i][j] += (dp[i - 1][j] + dp[i - 1][(j + 3 - m) % 3])%mod;
            }
        }
        /*最后打印出所有数字都加上之后能够被三整除的有多少个。
        System.out.println(dp[len][0]);
    }
}