1082 数字游戏（数位dp）

绝地灬酷狼 2022-09-14 08:39 141阅读 0赞

**1. 问题描述：**

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

**输入格式**

输入包含多组测试数据。每组数据占一行，包含两个整数 a 和 b。

**输出格式**

每行给出一组测试数据的答案，即 \[a,b\] 之间有多少不降数。

**数据范围**

1 ≤ a ≤ b ≤ 2 ^ 31 − 1

**输入样例：**

1 9  
1 19

**输出样例：**

9  
18  
来源：[https://www.acwing.com/problem/content/description/1084/][https_www.acwing.com_problem_content_description_1084]

**2. 思路分析：**

分析题目可以知道我们需要求解出某个区间中满足不降序列的个数，由这个特点可以知道属于**数位dp**的题目（数位dp的题目一般求解的是某个区间满足某种性质的数的个数），对于数位dp的题目分析方式都是类似的，我们都是采用树的形式来分析，可以参照[1081题度的数量][1081]。具体的实现步骤如下（数位dp的题目一般都可以采用下面的步骤）：我们一般求解的是区间\[0，n\]中满足某种性质的数的个数，所以对于区间\[x，y\]我们可以使用f(y) - f(x - 1)来求解，f为求解出\[0，n\]中不降数的个数的方法；以区间其中一个端点y为例，我们需要将y的每一位抠出来存储到列表nums中，然后逆序枚举nums中的每一位数字，也即从高位到低位枚举每一位数字，对于当前第i位数字x = nums\[i\]，我们可以尝试填0 ~ x-1，这样第i位后面随便填满足题目要求的数字，第i位填0 ~ x-1所以答案直接累加上当前有i + 1位数，最高位是j的方案数目即可（一般先通过预处理这样左边分支的方案数目可以直接计算出来，所以预处理是第一个步骤这样在枚举当前位为0~x-1的时候可以直接计算出结果），这里累加的其实是左边分支的数目，进入到循环的nums的下一位数字的时候表示第i位填的是x，对于数位dp的题目我们一般需要预处理一个二维数组，预处理的过程其实是一个递推的过程（本身就是一个动态规划），对于这道题目来说我们可以声明一个二维数组f，其中f\[i\]\[j\]表示最高位为j且总共有i位的不降数的个数，在递推的时候使用三层循环进行递推，第一层循环表示当前有i位数字，第二层循环表示i位数字的最高位填的是j，第三层循环枚举次高位的数字，从j开始枚举一直到9，这样才满足不降数的要求，一般左边分支的方案数目可以直接通过递推求解出来。

**3. 代码如下：**

from typing import List
    import sys
    
    
    class Solution:
        # f[i][j]表示最高位是j且总共有i位的不降数个数, 先预处理出来后面可以直接计算左边的那个分支
        def init(self, N: int, f: List[List[int]]):
            # 当前只有一位数字且最高位是i的方案数为1
            for i in range(10): f[1][i] = 1
            for i in range(2, N):
                for j in range(10):
                    # 因为当前位只与次高位有关所以只枚举次高位填什么即可, 次高位只能从j开始枚举表示不降数
                    for k in range(j, 10):
                        f[i][j] += f[i - 1][k]
    
        # 计算区间[0, n]不降数的个数
        def dp(self, n: int, f: List[List[int]]):
            # 特判一下
            if n == 0: return 1
            nums = list()
            # 将n的每一位存储到nums中
            while n > 0:
                nums.append(n % 10)
                n //= 10
            res, last = 0, 0
            for i in range(len(nums) - 1, -1, -1):
                x = nums[i]
                # 当前这一位填last ~ x-1的数字那么第i位之后的数字可以随便填, 这里随便填的意思是通过预处理得到的对应的方案数目
                for j in range(last, x):
                    # 注意应该是i + 1, 表示总共有i位
                    res += f[i + 1][j]
                # 当前第i位的数字小于last表示之后的方案都是不满足的, 可以直接举例子比较好理解
                if last > x: break
                # last当前这一位填的数字进入下一个循环的时候表示的就是上一次填的数字
                last = x
                # 最后那个分支的数目
                if i == 0: res += 1
            return res
    
        def process(self):
            N = 15
            f = [[0] * N for i in range(N)]
            self.init(N, f)
            while True:
                # 判断是否存在输入, 使用input()就无法通过
                s = sys.stdin.readline().strip()
                if not s: break
                s = s.split()
                a, b = int(s[0]), int(s[1])
                print(self.dp(b, f) - self.dp(a - 1, f))
    
    
    if __name__ == "__main__":
        Solution().process()

[https_www.acwing.com_problem_content_description_1084]: https://www.acwing.com/problem/content/description/1084/
[1081]: https://blog.csdn.net/qq_39445165/article/details/120575281