有点感觉了，总结一下，就是按位枚举，动态划分每一位的情况，状态表示出来

#include <iostream>
#include <vector>
using namespace std;

const int N=15;

//fij，所有最高位是j，一共i位的不降数的个数
int f[N][N];

int dp(int n)
{
    if(n==0) return 1;
    vector<int> nums;
    while(n)
    {
        nums.push_back(n%10);
        n=n/10;
    }
    int res=0;
    int last=0;
    for(int i=nums.size()-1;i>=0;i--)
    {
        int x=nums[i];
        for(int j=last;j<x;j++)
        {
            res+=f[i+1][j];
        }
        //如32以内的不降数和31以内的不降数 和29以内的不降数都是一样的
        if(last>x)
        break;

        last=x;

        if(i==0) res++;
    }
    return res;

}
int main()
{
    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++)//j要从0开始
            for(int k=j;k<=9;k++)
                f[i][j]+=f[i-1][k];

   int l,r;
   while(cin>>l>>r)
   {
       cout<<dp(r)-dp(l-1)<<endl;
   }

    return 0;
}

数位dp关键是要找一个递推式f[i][j]。事先把所有状态计算出来

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

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

int dp(int n)
{
    if(n==0) return 1;
    vector<int> num;
    while(n)
    {
        num.push_back(n%10);
        n=n/10;
    }
    int res=0;
    int last=0;
    for(int i=num.size()-1;i>=0;i--)
    {
        int x=num[i];
        for(int j=last;j<x;j++)
        {
            res+=f[i+1][j];
        }
        if(x<last) break;
        last=x;
        if(i==0) res++;    
    }


    return res;
}

int main()
{
    for(int i=0;i<=9;i++) f[1][i]=1;
    for(int i=2;i<=N-1;i++)
    {
        for(int j=0;j<=9;j++)
        {
            for(int k=j;k<=9;k++)
            {
                f[i][j]+=f[i-1][k];
            }
        }
    }
    int a,b;
    while(cin>>a>>b)
    {
        cout<<dp(b)-dp(a-1)<<endl;
    }

    return 0;
}

三刷

思路为
1. last表示的是上一位的数
2. f[i][j]表示的是一共i位(必须是i位，不能小于i位),首位为j的不降数的个数
3. 分三种情况
1. 如果x>last: 则可以枚举x到last-1的，位数为i+1的所有不降数个数
2. 如果x<last：说明枚举完了，可以直接结束
3. 如果x=last：什么也不要做，继续下一位
4. 注意如果遍历到最后还没有break，说明该数本身是一个不降数，res++

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int N=15;
int f[N][N];
int l,r;

int dp(int n)
{
    vector<int> num;

    while(n)
    {
        num.push_back(n%10);
        n=n/10;
    }
    int res=0;
    int last=1;
    for(int i=num.size()-1;i>=0;i--)
    {
        int x=num[i];

        if(x>last)
        {
            for(int j=last;j<x;j++)
            {
                res+=f[i+1][j];
            }
            last=x;
        }
        else if(x<last)
        {
            break;
        }
        if(i==0) res++;
    }
    //最后把所有位数小于num.size-1的的情况加上。
    if(num.size()>1)
    for(int i=1;i<=num.size()-1;i++)
    {
        for(int j=1;j<=9;j++)
        {
            res+=f[i][j];

        }
    }

    return res;
}

int main()
{
    for(int i=1;i<=9;i++)
    {
        f[1][i]=1;
    }
    for(int i=2;i<=N-1;i++)
    {
        for(int j=1;j<=9;j++)
        {
            for(int k=j;k<=9;k++)
            {
                f[i][j]+=f[i-1][k];
            }
        }
    }

    while(cin>>l>>r)
    {
        cout<<dp(r)-dp(l-1)<<endl;
    }

    return 0;
}