数位DP

模板题：1082. 数字游戏
题目描述
求整数区间 [L,R][L,R] 内， 不降数 的个数

不降数：数位从高到低呈非下降关系（【例】：123，446）

代码

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

typedef long long LL;
#define N 15
int f[N][N];//f[i][j]表示i位数且最高位(最左端为最高位)为j的不降序的方案数
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];
            //   cout<<i<<" "<<j<<" "<<f[i][j]<<endl;
           } 
}
int dp(int n){
    if(n==0) return 1;
    vector<int> nums;
    while(n) nums.push_back(n%10),n/=10;
    // cout<<n<<endl;
    // cout<<nums[0]<<endl;
    int ans=0;
    int last=0;
    for (int i=nums.size()-1; i>=0; i--){
        int x=nums[i];
        for(int j=last;j<x;j++)
           ans+=f[i+1][j];
        if(last>x) break;
        last=x;
         if(!i) ans++;//全部枚举到最低位的右分支。
    }
    return ans;
}

signed main()
{
    init();
    int n,m;
     while(cin>>n>>m)
    //  cout<<n<<m<<" "<<dp(n-1)<<endl;
      printf("%d\n",dp(m)-dp(n-1));
    return 0;
}