每日算法 — 使用java实现数位DP：动态规划统计区间满足条件的数字个数

引言

数位DP（Digit Dynamic Programming）是一种专门用于解决”统计区间[L, R]内满足某条件的数字个数”问题的动态规划技巧。这类问题如果直接遍历每个数字进行判断，在范围达到10^18时完全不可行。数位DP通过逐位构造数字，利用记忆化搜索将复杂度从O(R-L)降低到O(log R × 状态数)。本文将用Java实现数位DP框架，并以”统计区间内不含连续重复数字的个数”为例进行讲解。

算法核心思想

问题转化

统计区间[L, R]内满足条件的数字个数，可以转化为求f(R) - f(L-1)，其中f(X)表示[0, X]内满足条件的数字个数。这样问题统一为：给定上界X，统计[0, X]内满足条件的数字个数。

逐位构造与记忆化

将上界X按位拆分为数字数组（如X=345拆为[3,4,5]）。从最高位开始逐位填数，用DFS/记忆化搜索统计所有合法方案。

关键状态设计：
– pos：当前处理到的位数
– tight：是否紧贴上界（影响当前位可选范围）
– leadingZero：是否还在前导零阶段
– 其他状态：根据具体问题设计（如最后一位数字、数字和等）

记忆化优化

当tight=false且leadingZero=false时，当前状态的结果与具体上界无关，可以用记忆化数组存储，避免重复计算。

完整Java实现

import java.util.*;

/**
 * 数位DP（Digit DP）实现
 * 用于高效统计区间内满足特定条件的数字个数
 * 本例统计区间内"不含连续重复数字"的数字个数
 */
public class DigitDP {

    private long[][] memo;      // 记忆化数组 memo[pos][lastDigit]
    private int[] digits;       // 上界数字的各位

    /**
     * 核心DFS函数
     * @param pos 当前处理到的位（从最高位开始）
     * @param tight 是否受上界约束，true表示当前位不能超过上界对应位
     * @param leadingZero 是否处于前导零状态
     * @param lastDigit 上一位填的数字（用于判断连续性）
     * @return 从当前状态开始的合法方案数
     */
    private long dfs(int pos, boolean tight, boolean leadingZero, int lastDigit) {
        // 所有位都处理完毕，找到一个合法数字
        if (pos == digits.length) {
            return leadingZero ? 0 : 1;  // 排除全0的情况（根据题意决定）
        }

        // 记忆化：非受限且非前导零状态下，结果与上界无关
        if (!tight && !leadingZero && memo[pos][lastDigit + 1] != -1) {
            return memo[pos][lastDigit + 1];
        }

        long res = 0;
        // 当前位可选的最大数字
        int upperBound = tight ? digits[pos] : 9;

        for (int d = 0; d <= upperBound; d++) {
            boolean nextTight = tight && (d == upperBound);
            boolean nextLeadingZero = leadingZero && (d == 0);

            if (leadingZero && d == 0) {
                // 继续前导零状态，lastDigit保持无效
                res += dfs(pos + 1, nextTight, nextLeadingZero, -1);
            } else {
                // 非前导零状态
                // 条件判断：不能与前一位数字相同（不含连续重复数字）
                if (lastDigit != -1 && d == lastDigit) {
                    continue;  // 连续重复，跳过
                }
                res += dfs(pos + 1, nextTight, false, d);
            }
        }

        // 存储记忆化结果
        if (!tight && !leadingZero) {
            memo[pos][lastDigit + 1] = res;
        }

        return res;
    }

    /**
     * 计算[0, x]内不含连续重复数字的数字个数
     * @param x 上界
     * @return 满足条件的数字个数
     */
    public long countNoConsecutiveRepeats(long x) {
        if (x < 0) return 0;
        if (x == 0) return 1;  // 0本身没有连续重复

        // 将x拆分为各位数字
        String s = String.valueOf(x);
        digits = new int[s.length()];
        for (int i = 0; i < s.length(); i++) {
            digits[i] = s.charAt(i) - '0';
        }

        // 初始化记忆化数组
        // lastDigit范围：-1到9，用+1映射到0到10
        memo = new long[digits.length][11];
        for (long[] row : memo) {
            Arrays.fill(row, -1);
        }

        return dfs(0, true, true, -1);
    }

    /**
     * 计算区间[L, R]内不含连续重复数字的数字个数
     */
    public long countInRange(long L, long R) {
        return countNoConsecutiveRepeats(R) - countNoConsecutiveRepeats(L - 1);
    }

    // ==================== 扩展：统计数字各位之和为特定值的个数 ====================

    private long[][][] memoDigitSum;  // memo[pos][tight][digitSum]

    /**
     * 计算[0, x]内各位数字之和等于target的数字个数
     */
    public long countWithDigitSum(long x, int target) {
        if (x < 0) return 0;

        String s = String.valueOf(x);
        digits = new int[s.length()];
        for (int i = 0; i < s.length(); i++) {
            digits[i] = s.charAt(i) - '0';
        }

        // 注意：这里用Map做记忆化，因为digitSum范围不确定
        Map<String, Long> cache = new HashMap<>();
        return dfsDigitSum(0, true, 0, target, cache);
    }

    private long dfsDigitSum(int pos, boolean tight, int currentSum, int target, Map<String, Long> cache) {
        if (currentSum > target) return 0;  // 剪枝：和已超过目标

        if (pos == digits.length) {
            return currentSum == target ? 1 : 0;
        }

        String key = pos + "," + (tight ? 1 : 0) + "," + currentSum;
        if (!tight && cache.containsKey(key)) {
            return cache.get(key);
        }

        long res = 0;
        int upperBound = tight ? digits[pos] : 9;

        for (int d = 0; d <= upperBound; d++) {
            boolean nextTight = tight && (d == upperBound);
            res += dfsDigitSum(pos + 1, nextTight, currentSum + d, target, cache);
        }

        if (!tight) {
            cache.put(key, res);
        }
        return res;
    }

    /**
     * 主程序：演示数位DP
     */
    public static void main(String[] args) {
        DigitDP solver = new DigitDP();

        // 测试1：统计[1, 100]内不含连续重复数字的个数
        System.out.println("=== 不含连续重复数字统计 ===");
        long L = 1, R = 100;
        long result = solver.countInRange(L, R);
        System.out.printf("[%d, %d] 内不含连续重复数字的个数: %d%n", L, R, result);

        // 验证：遍历检查
        int verifyCount = 0;
        for (long i = L; i <= R; i++) {
            if (hasNoConsecutiveRepeats(i)) verifyCount++;
        }
        System.out.println("暴力验证结果: " + verifyCount);
        System.out.println("结果一致: " + (result == verifyCount));

        // 测试2：大区间测试
        System.out.println("\n=== 大区间测试 ===");
        L = 1; R = 1000000000000L;  // 10^12
        long start = System.currentTimeMillis();
        result = solver.countInRange(L, R);
        long elapsed = System.currentTimeMillis() - start;
        System.out.printf("[1, 10^12] 内不含连续重复数字的个数: %d%n", result);
        System.out.println("数位DP耗时: " + elapsed + "ms");

        // 测试3：数字和统计
        System.out.println("\n=== 数字和等于特定值统计 ===");
        long testX = 1000;
        int targetSum = 10;
        long count = solver.countWithDigitSum(testX, targetSum);
        System.out.printf("[0, %d] 内各位数字之和等于 %d 的个数: %d%n", testX, targetSum, count);

        // 验证
        int verifySum = 0;
        for (long i = 0; i <= testX; i++) {
            if (digitSum(i) == targetSum) verifySum++;
        }
        System.out.println("暴力验证结果: " + verifySum);
        System.out.println("结果一致: " + (count == verifySum));

        // 测试4：超级大区间
        System.out.println("\n=== 超大区间性能测试 ===");
        L = 1; R = Long.MAX_VALUE / 10;  // 约9×10^17
        start = System.currentTimeMillis();
        result = solver.countInRange(L, R);
        elapsed = System.currentTimeMillis() - start;
        System.out.printf("[1, 9×10^17] 内不含连续重复数字的个数: %d%n", result);
        System.out.println("数位DP耗时: " + elapsed + "ms");
    }

    /**
     * 暴力验证：检查数字是否不含连续重复数字
     */
    private static boolean hasNoConsecutiveRepeats(long x) {
        String s = String.valueOf(x);
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == s.charAt(i - 1)) return false;
        }
        return true;
    }

    /**
     * 计算数字各位之和
     */
    private static int digitSum(long x) {
        int sum = 0;
        while (x > 0) {
            sum += x % 10;
            x /= 10;
        }
        return sum;
    }
}

关键算法解析

1. 状态压缩与tight标志

tight标志是数位DP的核心。当tight=true时，当前位不能超过上界对应位；当tight=false时，当前位可以填0-9任意数字。一旦某一位填了小于上界的数字，后续所有位都不受约束（tight变为false）。

2. 前导零处理

leadingZero标志处理数字位数不足的情况。例如统计[0, 345]时，数字5被表示为”005″，前导零不应参与条件判断（如”连续重复”的判断）。

3. 记忆化条件

只有当tight=false时才能使用记忆化，因为tight=true时的可选范围依赖于具体上界。leadingZero同样影响状态，通常与tight一起作为记忆化的前提条件。

复杂度分析

相比暴力的O(R-L)，数位DP在处理10^18级别区间时优势巨大。

总结

数位DP是解决”区间数字统计”类问题的标准工具。其核心思想有三：

1. 差分转化：区间[L,R]转化为f(R)-f(L-1)
2. 逐位构造：从高位到低位逐位填数，用DFS枚举所有可能
3. 记忆化剪枝：非受限状态的结果可复用，避免重复计算

本文实现了两个经典应用场景：不含连续重复数字的统计、数字和等于特定值的统计。数位DP的框架高度可复用，只需调整条件判断和状态设计即可适配不同问题。