题目描述

Windy 定义了一种 Windy 数：不含前导零且相邻两个数字之差至少为 22 的正整数被称为 Windy 数。

Windy 想知道，在 A 和 B 之间，包括 A 和 B，总共有多少个 Windy 数？

输入格式
共一行，包含两个整数 A 和 B。

输出格式
输出一个整数，表示答案。

数据范围
1≤A≤B≤2×10^9
输入样例1：
1 10
输出样例1：
9

import java.util.*;
class Main{
    static int N = 11;
    static int[][] dp = new int[N][N];
    public static void init(){
        //总共1位， 最高位为i的个数为1
        for(int i = 0; i <= 9; i++) dp[1][i] = 1;
        for(int i = 2; i < N; i++){
            for(int j = 0; j <= 9; j++){
                for(int k = 0; k <= 9; k++){
                    if(Math.abs(j - k) >= 2)  dp[i][j] += dp[i - 1][k];
                }
            }
        }
    }

    public static int dp(int n){
        if(n == 0) return 0;
        List<Integer> list = new ArrayList();
        while(n > 0){
            list.add(n % 10);
            n /= 10;
        }
        int res = 0;
        int last = -2;
        //答案是a.size()位的
        for(int i = list.size() - 1; i >= 0; i--){
            int x = list.get(i);
            for(int j = i == list.size() - 1 ? 1: 0; j < x; j++){
                if(Math.abs(j - last) >= 2) res += dp[i + 1][j];
            }
            if(Math.abs(x - last) < 2) break;
            last = x;
            if(i == 0) res++;
        }
        //答案小于a.size()位的
        for(int i = 1; i < list.size(); i++) {
            for (int j = 1; j <= 9; j++) {
                res += dp[i][j];
            }
        }
        return res;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        init();
        int X = sc.nextInt(), Y = sc.nextInt();
        System.out.println(dp(Y) - dp(X - 1));
    }

}