数位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 ++) { //最高位, 初始化需要前导0for(int k = 0; k <= 9; k ++) {if(abs(j-k)>=2) f[i][j] += f[i-1][k];}} }}int dp(int n) {// 特判n == 0if(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 ++) { // 不能有前导0res += f[i][j];}}return res;
}int main() {init();int l, r;cin >> l >> r;cout << dp(r) - dp(l-1) << endl;return 0;
}