数位dp-acwing（数字游戏）

题目：数字游戏

1082. 数字游戏 - AcWing题库

分析：

前缀和思想: dp(m) - dp(n-1)

用树的角度分析。

比最高位小的， 左分支讨论，等于最高位的进入右分支，（同时进入右分支有条件，就是当前位最大值last <= x(下一位值，此高位）.

对于左分支，随便弄，只要后面的大于前面的就行（不会超过n的值）=>这个东西提前算好了，就是f[i][j] i位数，最高位是j，这种情况下满足性质有几位。

符合条件进入右分支。

如果能枚举完，还要加上特殊情况（ans ++);

代码:

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

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

void init() {
    for(int i = 0; i <= 9; i ++) f[1][i] = 1;
        
    for(int i = 2; i < N; i ++)  // 位数
        for(int j = 0; j <= 9; j ++)  // 最高位是多少
            for(int k = j; k <= 9; k ++) // 比最高位大
                f[i][j] += f[i-1][k]; // 下一位>=j的全加起来
}

int dp(int n) {
    // 特判n == 0,只有0这一种情况，因为n=0 后面循环无法通过存储nums
    if(!n) return 1;
    
    vector<int> nums;
    while(n) nums.push_back(n%10), n/=10;
    
    int ans = 0, last = 0; // 存上一个最大值
    for(int i = nums.size()-1; i >=0; i --) {
        int x = nums[i];
        // 进入右分支条件： x >= last
        // j >= last
        for(int j = last; j < x; j ++) {
            ans += f[i+1][j];
        }
        
        if(last>x) break;
        last = x;
        // 右子树进入到最后一个右分支，特殊处理（算一种情况）
        if(!i) ans ++;
    }
    return ans;
}

int main() {
    int n, m;
    
    init();
    
    while(cin >> n >> m) cout << dp(m) - dp(n-1) << endl;
    
    return 0;
}