数位DP题目：LeetCode1015. 至少有 1 位重复的数字

题目链接

给定正整数 N，返回小于等于 N 且具有至少 1 位重复数字的正整数。

示例 1：

输入：20
输出：1
解释：具有至少 1 位重复数字的正数（<= 20）只有 11 。
示例 2：

输入：100
输出：10
解释：具有至少 1 位重复数字的正数（<= 100）有 11，22，33，44，55，66，77，88，99 和 100 。
示例 3：

输入：1000
输出：262
 

提示：

1 <= N <= 10^9

解答：这是一道数位DP模板题，算法见代码注释。

//author: xnjxyk
int num[10], tot;
int dp[10][1024][2];

// flag表示当前搜索结果中整数的位数是否和N一样
// lead表示当前搜索整数是否有前导0
// succ表示枚举这一位以前有没有重复
// state换算成二进制有10位，分别表示枚举到这一位之前0~9有没有被使用
// now表示当前枚举位置
int dfs(int now, int state, int succ, bool lead, bool flag){
    // 如果枚举完最后一位，那么返回succ，succ=1表示有重复的数字，succ=0表示没有重复的数字
    if (now==0) {
        printf("State = %d (%d)\n", state, succ);
        return succ;
    }
    // 记忆化，如果位数小于N，没有前导0，而且结果已经被求出来，则直接返回
    if (flag==false && lead==false && dp[now][state][succ]!=-1) return dp[now][state][succ];

    int lim=((flag==false)?9:num[now]);// 如果位数一样，则搜索上限是num[now]，如果位数小于N，则搜索上限是9
    // 返回结果清零
    int ret=0;
    // 如果有前导0，那么这位只能从1开始枚举，如果没有前导0，则可以从0开始枚举
    for (int i=(lead?1:0); i<=lim; i++){
        // state|(1<<i)记录当前枚举的数字，succ|((state>>i)&1)记录当前枚举数字以后，会不会有重复
        // 这两个运算是本题数字DP的关键
        ret+=dfs(now-1, state|(1<<i), succ|((state>>i)&1), false, (flag && i==lim));
    }
    // 对应前面的记忆化
    if (flag==false && lead==false) dp[now][state][succ]=ret;
    return ret;
}

class Solution {
public:
    int numDupDigitsAtMostN(int N) {
        memset(dp, -1, sizeof(dp));
        // tot表示正整数N一共有多少位
        tot=0; while(N) num[++tot]=N%10, N/=10;
        int ans=0;
        for (int i=tot; i>=1; i--)
            ans+=dfs(i, 0, 0, true, i==tot);
        return ans;
    }
};