解题思路
本题要求统计不大于 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;