数位dp-acwing

题目：Windy数

1083. Windy数 - AcWing题库

分析

不能有前导0，初始化的时候需要有前导0，因为除了最高位数其他位数可以。

windy ： 2 5 1 类似这样的数 第二位与第一位相差3 >= 2

分类讨论 ：

1. 位数跟 n 同位数 的 

二叉树： 左子树情况， 右子树情况（看是否能进入，就是abs(x-last) >= 2才能进，不能就break)

2. 位数< n 数字的位数的

遍历一遍，位数 ＋ 最高位1-9 

代码

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

const int N = 15;
int f[N][N];

void init() {
    // 只有一位 最高位自身1个
    for(int i = 0; i <= 9; i ++) f[1][i] = 1;
    // 位数枚举 2e9  十位数字
    for(int i = 2; i <= 10; i ++) { // 位数
        for(int j = 0; j <= 9; j ++) { //最高位, 初始化需要前导0
            for(int k = 0; k <= 9; k ++) {
                if(abs(j-k)>=2) f[i][j] += f[i-1][k];
            }
        } 
    }
    
}

int dp(int n) {
    // 特判n == 0
    if(n == 0) return 0; // 当n == 0时，第二个循环会死循环
    int res = 0, last = -1;
    vector<int> nums;
    while(n) nums.push_back(n%10), n/=10;
    // nums.size() 位数的
    for(int i = nums.size()-1; i >= 0; i --) {
        int x = nums[i];
        // 最高位 从1(不能前导0) 开始枚举(i==nums.size()-1);
        // 左子树
        for(int j = (i==nums.size()-1); j < x; j ++) {
            if(abs(j-last)>=2) res += f[i+1][j];
        }
        // 右子树
        if(abs(x-last)<2) break; 
        last = x;
        // 特殊情况 全枚举（本身）
        if(!i) res ++; 
    }
    // < nums.size() 位数的 0 - nums.size()-2  但是向右偏移，位数来算，原本是下标
    for(int i = 1; i <= nums.size()-1; i ++) {
        for(int j = 1; j <= 9; j ++) { // 不能有前导0
            res += f[i][j];
        }
    }
    
    return res;
}

int main() {
    init();
    int l, r;
    cin >> l >> r;
    cout << dp(r) - dp(l-1) << endl;
    return 0;
}