[数据结构与算法]美团笔试：判断一个数的全排列是否能被22整除（动态规划）

整除
时间限制： 5000MS
内存限制： 655360KB
题目描述：
小美最近迷上了22这个数字，一天，她发现他的一本书中有一个神秘的大数字。于是她想知道这个数字中有多少子串代表的数字能被22整除。

输入描述
一行一个只由数字组成的不含前导零的字符串，字符串长度为 n(1≤n≤105)。

输出描述
一行一个整数代表有多少这个字符串的子串代表的数字能被 22 整除。

样例输入
12221
样例输出
2

提示
样例解释

[2,3] [3,4] 代表的子串为22，可以被22整除。

// 判断一个str的全排列，有多少能被22整除
    /*
    动态规划
    dp[i][j]：代表str的[i,j]的长度是否能被22整除
    初始化：dp[0][1]=false,dp[1][2]=false等等
    动态转移方程：
    dp[i][j]是否能被22整除
        dp[i][j-1]等于true
            dp[i][j]=false&&yuShu[i][j] = [j-1,j]
        dp[i][j-1]等于false
            判断yuShu[j][j-1]是否>22
                大于：dp[i][j]=false&&后面都不需要判断,都是false
                小于：dp[j][j]=(yuShu[i][j-1]*10+dp[j-1][j])%22 是否等于0
     */
    public static int ZhengChu(String str) {
        int res = 0;
        // dp[i][j]代表字符串[i,j)是否能被22整除
        boolean[][] dp = new boolean[str.length()][str.length() + 1];
        // yuShu[i][j]代表字符串[i,j)被22整除，剩余的余数
        int[][] yuShu = new int[str.length()][str.length() + 1];
        for (int i = 0; i < str.length(); i++) {
            for (int j = i + 1; j <= str.length(); j++) {
                // 代表的[j-1,j]这个数字
                int val = Integer.parseInt(str.substring(j - 1, j));
                // 初始化
                if (j == i + 1) {
                    dp[i][j] = false;
                    yuShu[i][j] = val;
                }
                if (dp[i][j - 1]) {
                    dp[i][j] = false;
                    yuShu[i][j] = val;
                } else {
                    if (yuShu[i][j - 1] > 22) {
                        dp[i][j] = false;
                        break;
                    } else {
                        int yu = (yuShu[i][j - 1] * 10 + val) % 22;
                        if (yu==0){
                            dp[i][j] = true;
                            System.out.println(str.substring(i,j));
                            res++;
                        }
                        yuShu[i][j] = yu;
                    }
                }
            }
        }
        return res;
    }