[数据结构与算法]数位动态规划

数位动态规划能够解决的问题需要符合以下特征：

1. 要求统计满足一定条件的数的数量（即，最终目的为计数）；
2. 这些条件经过转化后可以使用「数位」的思想去理解和判断；
3. 输入会提供一个数字区间（有时也只提供上界）来作为统计的限制；
4. 上界很大（比如 ），暴力枚举验证会超时。

数位动态规划思路就是按照以下三种情况去思考问题

假设需要求解数字位数是n,而取值限制数组limit,长度为m

x为待构建数字位数

则 x==n时候，如果某第p位置的数字<(n所在位置r的数)，此时该位置的取值公式应为：

(r+1)*(int)Math.pow(m,(n-p));

含义是该位置能够放置的数字个数为r+1(注意下标从0开始，所以是r+1)

除了该p位置，其余位置都能够随便放置m里的任意数值，位置p之后还剩下位置数为（n-p）,所以其总选择为Math.pow(m,(n-p)。

这俩个位置相乘为位置p数字小于limit数组中r位置的总可选择个数。

获得到该数值，则break调循环，即为长度为n的最终获取个数。

x==n的时候，如果某第p位置的数字都需要==(n所在位置的数r)，此时该位置的取值公式应为：

r*(int)Math.pow(m,(n-p));

含义是该位置能够放置的数字个数为r(注意下标从0开始，r位置数字不能够获取，否则其它位置无法随意获取值)

除了该p位置，其余位置都能够随便放置m里的任意数值，位置p之后还剩下位置数为（n-p）,所以其总选择为Math.pow(m,(n-p)。

这俩个位置相乘为位置p数字小于limit数组中r位置的总可选择个数。

注意这个时候p位置等于limit[r]的个数仍然没有计算到结果里面，仍然需要重复下一个位置p+1，计算小于p+1位置的个数加上p位置的结果才是长度为n的完整的结果集，如果位置p+1位置的值在limit数组当中仍然找到了相同值的位置t，则我们继续寻找下一个位置p+2。

x<n的时候，每一个位置都不受n的限制，可以在符合题意范围内任意取值。

每一个位置的取值都可以是m

m*m*m(x个m)。(0<x<n)

下面看下这道题：

给定一个按 非递减顺序 排列的数字数组 digits 。你可以用任意次数 digits[i] 来写的数字。例如，如果 digits = ['1','3','5']，我们可以写数字，如 '13', '551', 和 '1351315'。

返回 可以生成的小于或等于给定整数 n 的正整数的个数 。示例 1：

输入：digits = ["1","3","5","7"], n = 100

输出：20

解释： 可写出的 20 个数字是： 1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.

提示：

• 1 <= digits.length <= 9
• digits[i].length == 1
• digits[i] 是从 '1' 到 '9' 的数
• digits 中的所有值都 不同
• digits 按 非递减顺序 排列
• 1 <= n <= 109

这道题的含义是在digits这个范围内构建小于n的数字

如果采用爆搜，一定要超时，这道题可以采用数位dp的方式来求解。

首先我们思考如果构建三位数字。

我们在思考一个用例：

digits = ["1","3","5","7"], n = 472

情况1，

一、构建长度为3的数字

第一个位置 4

<=4的位置r=1

3<4,所以（1+1）*(int)Math.pow(4,(3-1));

2*16=32

break掉循环

二、构建长度为2

则每一个位置都可以是digits里面的任意数字

选择个数为4,4*4=16

三、构建如果长度为1，

则每一个位置都可以在digits里面任意选择，

结果为4

32+16+4=45+20=52

再思考用例：digits = ["1","3","5","7"], n = 372

第一个位置 3

<=3的位置r=1

3==3,所以1*(int)Math.pow(4,(3-1));

16

第二个位置 7

<=7的位置r=3,由于digits[3]==7,

所以3*(int)Math.pow(4,(2-1));

3*4=12

第三个位置 2

<=2的位置0

由于digits[0]<2

所以按照题意这块是0，但是2在372的最后一个位置，如果获取到一个数字也应该记录到结果当中

所以这块要特殊处理在结果集当中加1

1

这个就是长度为3的结果总和

二、构建长度为2

则每一个位置都可以是digits里面的任意数字

选择个数为4,4*4=16

三、构建长度为1，

则每一个位置都可以在digits里面任意选择，

结果为4

结果为16+12+1+16+4=29+20=49

通过这几个例子不知你是否对这个数位dp有感觉。

????????唯一复杂的是在求解长度为n的数字时候找到了某个位置t的值在limit里面有相同值的时候，还要继续向下求解值，因为这个相同的值不能立马放置到结果集当中，其值是后面位置能够获取的最大个数。这样就有了以上的思路。