DP 数位 - wenzhoullq/leetcode GitHub Wiki

模板

数位DP用记忆化的方式比较好，数位DP的本质是这个数字的选择对后续的影响，有三个比较关键的点，一个是memo数组，一个是有无限制，一个是是否为数字(是否为数字指的是前导零)，注意limit和isnum的变化即可。

int[][] dp;
    char[] str;
    int len;
    public int findIntegers(int n) {
        String s=String.valueOf(n);
        int len=s.length();
        dp=new int[len][];
        for(int i=0;i<len;i++) Arrays.fill(dp[i],-1);
        return dfs(0,true,false);// 这里的true和false牢记
    }
    int dfs(int index,boolean islimit,boolean isnum){
        if(index==len) return 根据不同情况return的值不同
        if(isnum&&!islimit&&dp[index][]>0) return dp[index][];
        int ans=0;
        if(!isnum) ans+=dfs(index+1,false,false);
        for(int i=isnum?1:0,up=islimit?str[index]-'0':9;i<=up;i++){
            if() continue;
            ans+=dfs(index+1,islimit&&i==up,true);
        }
        if(isnum&&!islimit) dp[index][]=ans;
        return ans;
    }
}

题目

面试题 17.06. 2出现的次数 index==len的时候return的值不同

233. 数字 1 的个数

600. 不含连续1的非负整数 特殊一点，转化为二进制

902. 最大为 N 的数字组合

1012. 至少有 1 位重复的数字 至少有一位的补集是一位都没有

2376. 统计特殊整数