会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
本题要求统计不大于 N 的流畅数个数，N 的位数最多可达 105，直接暴力枚举不可行，因此需要采用数位 DP（动态规划）来解决。
- 状态定义
定义递归函数 dp(pos,last,isLimit,isNum)，其中：
- pos：当前构造到第 pos 位数（从高位向低位，pos 从 0 开始）；
- last：上一位选择的数字（0∼9）。特别地，在还没有选择任何数字时，用 last=0 作为占位（后续会通过 isNum 区分）；
- isLimit：布尔值，表示当前是否受到 N 的限制。若为真，则当前位只能填 0∼s[pos]（s[pos] 为 N 当前位的数字）；否则可以填 0∼9；
题目内容
在数字王国中，如果一个正整数的十进制表示里任意两个相邻数字都不相同，则称这个数为“流畅数”。例如，1234 是流畅数，而 112 和 1223 不是。
现在给定一个正整数 N，请你计算所有不大于 N 的正整数中，流畅数的个数。由于答案可能很大，请将其对 109+7 取模后输出。
数据范围：N 的十进制位数不超过 105。
输入描述
