动态规划-数位DP

一些题目有这样的规律：求一段区间内xx的个数是多少。xx描述了要求的数具有的性质。假设求[l, r]这个区间，可以处理成求dp(r) - dp(l - 1)。

例：科协里最近很流行数字游戏。某人命名了一种不降数，这种数字必须满足从左到右各位数字成小于等于的关系，如 123，446。现在大家决定玩一个游戏，指定一个整数闭区间 [a,b]，问这个区间内有多少个不降数。

现在假设一个n位数为N，我们求1~N之间的不降数数量。
将N按数位从高到低拆开。
可以使用vector来存while (n) nums.push_back(n % 10), n /= 10;

我们有有计划地枚举0~N的所有数。在最高位时，两种划分方式，一是填0 ~ a n − 1 − 1 a_{n-1}-1 an−1​−1，后面的数位上的数就可以没有限制地填了；另一种是填 a n − 1 a_{n-1} an−1​，这时候就要看第2高位如何填，也是两种划分方式，0 ~ a n − 2 − 1 a_{n-2}-1 an−2​−1， a n − 2 a_{n-2} an−2​。以此类推…

目前的状态已经被划分成了：
1，最高位填0~2，后面随便填的所有方案。
2，最高位填3，且次高位填0~3，后面随便填的所有方案。
3，最高位填3，且次高位填4，第三位填0~4，后面随便填的所有方案
4，最高位填3，且次高位填4，第三位填5，第四位填0~5，后面随便填的所有方案
5，最高位填3，且次高位填4，第三位填5，第四位填6，第五位填0~6的所有方案。
6，最高位填3，且次高位填4，第三位填5，第四位填6，第五位填7的方案。即填N。

注意：由于N比较特殊，是一个不降数，所以我们能枚举出所有方案。当N=34543时，我们枚举不到第四位填4的情况。 为了简便计算，我们要预处理一个数组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];
}

最终代码：

#include
#include
#include
#include
using namespace std;

const int N = 35;

int l, r;
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];
}

int dp(int n)
{
    if (!n) return 1;
    vector<int> nums;
    while (n) nums.push_back(n % 10), 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];
        if (x < last) break;
        last = x;
        if (!i) res ++ ;
    }
    
    return res;
}

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