数位DP
如果一个正整数每一个数位都是 互不相同 的，我们称它是 特殊整数 。
给你一个 正 整数 n ，请你返回区间 [1, n] 之间特殊整数的数目。
对于dp问题而言，每个状态都是由上个状态推导出来的。所以分析dp问题常常可以分为以下几步：
- 如何确定dp数组，数组下标都代表什么意思
- dp数组如何初始化
- 递推公式如何确定
- 如何遍历到目标情况
对于上面这道问题，我们可以发现n = 20可以由 n = 19递推而来。并且我们可以发现这可以算是一种数位dp问题。对于数位dp的解释，让我们用GPT帮我们下个简单易懂的定义:
数位 DP（Dynamic Programming）问题是一类动态规划问题，通常用于解决与数字的各个位相关的计数或优化问题。在这类问题中，我们会使用动态规划来记忆化搜索过程，以避免冗余计算。
典型的数位 DP 问题可能涉及到以下方面：
- 位数限制： 在数字中每一位的取值范围受到限制。
- 状态转移： 对于每一位的可能取值，定义状态转移方程。
- 记忆化搜索： 使用数组或哈希表等数据结构来保存已经计算过的结果，避免重复计算。
接下来给出灵神的数位DP模板
func countSpecialNumbers(n int) int {
str := strconv.Itoa(n)
l := len(str)
memo := make([][]int,l)
for i := 0; i < l; i++{
memo[i] = make([]int,1 << 10)
for j := range memo[i]{
memo[i][j] = -1
}
}
var dfs func(int,int,bool,bool)int
dfs = func(i,mask int,isLimit,isNum bool)(res int){
if i == l{
if isNum{
return 1
}
return
}
if !isNum{
res += dfs(i+1,mask,false,false)
}
if !isLimit && isNum && memo[i][mask] != -1{
return memo[i][mask]
}
d := 0
if !isNum{
d = 1
}
up := 9
if isLimit{
up = int(str[i] - '0')
}
for ; d <= up; d++{
if mask>>d&1 == 0{
res += dfs(i+1,mask | 1 << d,isLimit && d == up,true)
}
}
return
}
return dfs(0,0,true,false)
}
代码细节
将 n转换成字符串str，定义 dfs(i,mask,isLimit,isNum)表示构造第 i 位及其之后数位的合法方案数，其余参数的含义为：
- mask 表示前面选过的数字集合，换句话说，第 i 位要选的数字不能在 mask 中。
- isLimit表示当前是否受到了 n的约束（注意要构造的数字不能超过 n）。若为真，则第 i位填入的数字至多为 s[i]，否则可以是 9。如果在受到约束的情况下填了 s[i]，那么后续填入的数字仍会受到 n 的约束。例如n=123，那么 i=0 填的是 1 的话，i=1的这一位至多填 2。
- isNum 表示 i前面的数位是否填了数字。若为假，则当前位可以跳过（不填数字），或者要填入的数字至少为 1；若为真，则要填入的数字可以从 0 开始。例如 n=123，在 i=0 时跳过的话，相当于后面要构造的是一个 99 以内的数字了，如果 i=1不跳过，那么相当于构造一个 10到 99的两位数，如果 i=1 跳过，相当于构造的是一个 9 以内的数字。
dfs(0,0,true,false)表示：
- 从
str[0]开始枚举； - 一开始集合中没有数字；
- 一开始要受到约束（否则就可以随意填了，这肯定不行）；
- 一开始没有填数字。
递归中：
- 如果 isNum 为假，说明前面没有填数字，那么当前也可以不填数字。一旦从这里递归下去，isLimit 就可以置为 false 了，这是因为 s[0]必然是大于 0的，后面就不受到 n的约束了。或者说，最高位不填数字，后面无论怎么填都比 n 小。
- 如果 isNum 为真，那么当前必须填一个数字。枚举填入的数字，根据 isNum 和 isLimit来决定填入数字的范围。
递归终点：当 i 等于 s 长度时，如果 isNum为真，则表示得到了一个合法数字（因为不合法的不会继续递归下去），返回 1，否则返回 0。
