数位 DP

• OI Wiki: https://oi-wiki.org/dp/number/

题目	难度
POJ2282		计算 a 和 b 之间每个数字出现的次数
233. 数字 1 的个数	困难
面试题 17.06. 2 出现的次数	困难	类似 233
$1067. 范围内的数字计数	困难	类似 233
357. 统计各位数字都不同的数字个数	中等	可打表
600. 不含连续 1 的非负整数	困难
902. 最大为 N 的数字组合	困难
1012. 至少有 1 位重复的数字	困难
1397. 找到所有好字符串	困难	结合 KMP
2376. 统计特殊整数	困难	同 1012

定义

233. 数字 1 的个数

import java.util.Arrays;

public class Solution233 {
    private char[] s;
    private int[][] dp;

    // 数位 DP
    public int countDigitOne(int n) {
        s = String.valueOf(n).toCharArray();
        int len = s.length;
        dp = new int[len][10];
        for (int i = 0; i < len; i++) {
            Arrays.fill(dp[i], -1);
        }
        return f(0, 0, true, false);
    }

    private int f(int i, int sum, boolean isLimit, boolean isNum) {
        if (i == s.length) {
            return isNum ? sum : 0;
        }
        // 记忆化搜索
        if (!isLimit && isNum && dp[i][sum] >= 0) {
            return dp[i][sum];
        }
        int res = 0;
        if (!isNum) {
            // 可以跳过当前数位
            res = f(i + 1, sum, false, false);
        }
        int up = isLimit ? s[i] - '0' : 9;
        for (int d = isNum ? 0 : 1; d <= up; d++) {
            res += f(i + 1, sum + (d == 1 ? 1 : 0), isLimit && d == up, true);
        }
        if (!isLimit && isNum) {
            dp[i][sum] = res;
        }
        return res;
    }
}

面试题 17.06. 2 出现的次数

import java.util.Arrays;

public class SolutionI1706 {
    private char[] s;
    private int[][] dp;

    public int numberOf2sInRange(int n) {
        s = String.valueOf(n).toCharArray();
        int len = s.length;
        dp = new int[len][10];
        for (int i = 0; i < len; i++) {
            Arrays.fill(dp[i], -1);
        }
        return f(0, 0, true, false);
    }

    private int f(int i, int sum, boolean isLimit, boolean isNum) {
        if (i == s.length) {
            return isNum ? sum : 0;
        }
        // 记忆化搜索
        if (!isLimit && isNum && dp[i][sum] >= 0) {
            return dp[i][sum];
        }
        int res = 0;
        if (!isNum) {
            // 可以跳过当前数位
            res = f(i + 1, sum, false, false);
        }
        int up = isLimit ? s[i] - '0' : 9;
        for (int d = isNum ? 0 : 1; d <= up; d++) {
            res += f(i + 1, sum + (d == 2 ? 1 : 0), isLimit && d == up, true);
        }
        if (!isLimit && isNum) {
            dp[i][sum] = res;
        }
        return res;
    }
}

$1067. 范围内的数字计数

import java.util.Arrays;

public class Solution1067 {
    private int x;

    public int digitsCount(int d, int low, int high) {
        x = d;
        return countDigitOne(high) - countDigitOne(low - 1);
    }

    private char[] s;
    private int[][] dp;

    private int countDigitOne(int n) {
        s = String.valueOf(n).toCharArray();
        int len = s.length;
        dp = new int[len][10];
        for (int i = 0; i < len; i++) {
            Arrays.fill(dp[i], -1);
        }
        return f(0, 0, true, false);
    }

    private int f(int i, int sum, boolean isLimit, boolean isNum) {
        if (i == s.length) {
            return isNum ? sum : 0;
        }
        // 记忆化搜索
        if (!isLimit && isNum && dp[i][sum] >= 0) {
            return dp[i][sum];
        }
        int res = 0;
        if (!isNum) {
            // 可以跳过当前数位
            res = f(i + 1, sum, false, false);
        }
        int up = isLimit ? s[i] - '0' : 9;
        for (int d = isNum ? 0 : 1; d <= up; d++) {
            res += f(i + 1, sum + (d == x ? 1 : 0), isLimit && d == up, true);
        }
        if (!isLimit && isNum) {
            dp[i][sum] = res;
        }
        return res;
    }
}

600. 不含连续 1 的非负整数

import java.util.Arrays;

public class Solution600 {
    private char[] s;
    private int[][] dp;

    public int findIntegers(int n) {
        // 二进制字符串
        s = Integer.toBinaryString(n).toCharArray();
        int len = s.length;
        dp = new int[len][2];
        for (int i = 0; i < len; i++) {
            Arrays.fill(dp[i], -1);
        }
        return 1 + f(0, 0, true, false);
    }

    private int f(int i, int pre, boolean isLimit, boolean isNum) {
        if (i == s.length) {
            return isNum ? 1 : 0;
        }
        // 记忆化搜索
        if (!isLimit && isNum && dp[i][pre] >= 0) {
            return dp[i][pre];
        }
        int res = 0;
        if (!isNum) {
            // 可以跳过当前数位
            res = f(i + 1, pre, false, false);
        }
        int up = isLimit ? s[i] - '0' : 1;
        for (int d = isNum ? 0 : 1; d <= up; d++) {
            if (pre == 1 && d == 1) {
                break;
            }
            res += f(i + 1, d, isLimit && d == up, true);
        }
        if (!isLimit && isNum) {
            dp[i][pre] = res;
        }
        return res;
    }
}

902. 最大为 N 的数字组合

import java.util.Arrays;

public class Solution902 {
    private String[] digits;
    private char[] s;
    private int[] dp;

    public int atMostNGivenDigitSet(String[] digits, int n) {
        this.digits = digits;
        s = String.valueOf(n).toCharArray();
        int len = s.length;
        dp = new int[len];
        Arrays.fill(dp, -1);
        return f(0, true, false);
    }

    private int f(int i, boolean isLimit, boolean isNum) {
        if (i == s.length) {
            return isNum ? 1 : 0;
        }
        // 记忆化搜索
        if (!isLimit && isNum && dp[i] >= 0) {
            return dp[i];
        }
        int res = 0;
        if (!isNum) {
            // 可以跳过当前数位
            res = f(i + 1, false, false);
        }
        char up = isLimit ? s[i] : '9';
        for (String digit : digits) {
            char d = digit.charAt(0);
            // 枚举要填入的数字 d
            if (d > up) {
                break;
            }
            res += f(i + 1, isLimit && d == up, true);
        }
        if (!isLimit && isNum) {
            dp[i] = res;
        }
        return res;
    }
}

1012. 至少有 1 位重复的数字

import java.util.Arrays;

public class Solution1012 {
    private char[] s;
    private int[][] dp;

    public int numDupDigitsAtMostN(int n) {
        s = String.valueOf(n).toCharArray();
        int len = s.length;
        dp = new int[len][1 << 10];
        for (int i = 0; i < len; i++) {
            Arrays.fill(dp[i], -1);
        }
        return n - f(0, 0, true, false);
    }

    private int f(int i, int state, boolean isLimit, boolean isNum) {
        if (i == s.length) {
            return isNum ? 1 : 0;
        }
        // 记忆化搜索
        if (!isLimit && isNum && dp[i][state] >= 0) {
            return dp[i][state];
        }
        int res = 0;
        if (!isNum) {
            // 可以跳过当前数位
            res = f(i + 1, state, false, false);
        }
        int up = isLimit ? s[i] - '0' : 9;
        for (int d = isNum ? 0 : 1; d <= up; d++) {
            // 枚举要填入的数字 d
            if ((state >> d & 1) == 0) {
                // d 不在 mask 中
                res += f(i + 1, state | (1 << d), isLimit && d == up, true);
            }
        }
        if (!isLimit && isNum) {
            dp[i][state] = res;
        }
        return res;
    }
}

1397. 找到所有好字符串

import java.util.Arrays;

public class Solution1397 {
    private static final long MOD = 1000000007;
    private char[] s1c;
    private char[] s2c;
    private char[] evilc;
    private long[][] dp;
    private int[] next;

    public int findGoodStrings(int n, String s1, String s2, String evil) {
        this.s1c = s1.toCharArray();
        this.s2c = s2.toCharArray();
        this.evilc = evil.toCharArray();

        int m = evil.length();
        dp = new long[n][m];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], -1);
        }
        this.next = getNext(evil);

        return (int) f(0, 0, true, true);
    }

    private long f(int i, int stats, boolean downLimit, boolean upLimit) {
        if (i == s1c.length) {
            return 1;
        }
        // 记忆化搜索
        if (!downLimit && !upLimit && dp[i][stats] != -1) {
            return dp[i][stats];
        }
        long res = 0;
        char down = downLimit ? s1c[i] : 'a';
        char up = upLimit ? s2c[i] : 'z';
        for (char ch = down; ch <= up; ch++) {
            int nextStats = getNextStats(stats, ch);
            if (nextStats == evilc.length) {
                continue;
            }
            res += f(i + 1, nextStats, downLimit && ch == s1c[i], upLimit && ch == s2c[i]);
            res %= MOD;
        }

        if (!downLimit && !upLimit) {
            dp[i][stats] = res;
        }
        return res;
    }

    // KMP
    private int getNextStats(int stats, char ch) {
        while (stats != 0 && evilc[stats] != ch) {
            stats = next[stats - 1];
        }
        return (evilc[stats] == ch) ? stats + 1 : 0;
    }

    // KMP 前缀函数
    // https://oi-wiki.org/string/kmp/
    private int[] getNext(String s) {
        int[] next = new int[s.length()];
        for (int i = 1, j = 0; i < s.length(); i++) {
            while (j > 0 && s.charAt(i) != s.charAt(j)) {
                j = next[j - 1];
            }
            if (s.charAt(i) == s.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }
}

（全文完）