Python数位DP教程：解决大范围数位和计数问题-Python教程-PHP中文网

Python数位DP教程：解决大范围数位和计数问题

本文介绍了如何使用数位动态规划（digit dp）高效解决在大数值范围（n可达10^12）内，统计数位和小于等于给定值x的整数数量的问题。针对传统遍历方法的低效性，文章详细阐述了基于递归与记忆化搜索的数位dp算法原理，并通过具体示例和python代码，指导读者实现一个高性能的解决方案，适用于处理大规模数据场景下的数位条件计数挑战。

问题概述

在计算机科学中，我们经常会遇到需要统计满足特定条件的数字数量的问题。一个常见的挑战是，在给定一个大范围 [1, n] 和一个上限 x 的情况下，计算所有整数 i (其中 1

传统方法的局限性

一个直观的解决方案是遍历从 1 到 n 的每一个数字，计算其数位和，然后判断是否满足条件。示例如下：

def digitsums_lower_than_x_naive(x, n):
    digit_sum = lambda y: sum(int(digit) for digit in str(y))
    # 题目要求1到n，这里+1是为了包含0，因为数位DP通常从0开始计数
    # 实际应用中，如果题目要求1到n，需要对0进行特殊处理或减去DS(x, 0)
    return sum(1 for i in range(1, n + 1) if digit_sum(i) <p>尽管此函数对于小范围的 n 能给出正确结果，但其时间复杂度为 O(n * log(n))（log(n) 是计算数位和的时间），对于 n 达到 10^12 这样的量级，这种方法将极其低效，无法在实际应用中接受。我们需要一种更高效的算法。</p><h2>核心算法：数位动态规划（Digit DP）</h2><p>为了解决大范围内的数位和计数问题，我们通常采用数位动态规划（Digit DP）的方法。数位DP的核心思想是将一个大数的计数问题分解为子问题，通过递归地处理数字的每一位，并利用记忆化搜索（memoization）避免重复计算。</p><h3>基本思想</h3><p>数位DP通过从最高位到最低位逐位构建数字来计数。在构建过程中，我们维护当前已构建部分的数位和，以及一个标志位来指示当前数字是否仍然受原始上限 n 的限制（即是否为“紧”状态）。</p><p>对于本问题，我们可以定义一个函数 DS(max_digit_sum, upper_bound_num)，它返回在范围 [0, upper_bound_num] 中，数位和小于等于 max_digit_sum 的整数数量。</p><h3>递归关系与状态定义</h3><p>考虑计算 DS(max_s, N)，其中 max_s 是允许的最大数位和，N 是一个字符串形式的上限数字。</p><p>我们可以将 N 拆解为最高位 D 和剩余部分 N'。例如，如果 N = 112，则 D = 1，N' = 12。</p><p>为了计算 DS(max_s, N)，我们可以考虑所有可能的最高位 d：</p><ol>
<li><strong>当 d ：当前数字的最高位小于 N 的最高位。这意味着从当前位开始，后续的数字位可以自由选择从 0 到 9，直到数字的末尾。此时，问题转化为计算一个长度比 N 少一位的“全9”数字（例如 99...9）的数位和计数，且允许的最大数位和为 max_s - d。</strong></li>
<li>
<strong>当 d == D 时</strong>：当前数字的最高位等于 N 的最高位。这意味着后续的数字位仍然受到 N 的剩余部分 N' 的限制。此时，问题转化为计算 DS(max_s - d, N')。</li>
</ol><p>通过这种方式，DS(max_s, N) 可以分解为多个子问题的和。</p><h3>示例解析：DS(5, 112)</h3><p>我们以 DS(5, 112) 为例，来演示数位DP的分解过程。这里 max_s = 5，N = "112"。</p><ol>
<li>
<p><strong>DS(5, "112")</strong>：</p>
<ul>
<li><p>N 的最高位 D = 1。</p></li>
<li><p>遍历可能的最高位 d 从 0 到 min(max_s, D)，即 0 到 1。</p></li>
<li>
<p><strong>当 d = 0 时</strong>：</p>
<ul>
<li>当前最高位 0 小于 N 的最高位 1。</li>
<li>问题转化为计算一个两位数（99）的数位和计数，最大数位和为 5 - 0 = 5。即 DS(5, "99")。</li>
</ul>
</li>
<li>
<p><strong>当 d = 1 时</strong>：</p><div class="aritcle_card flexRow artxards">
											<div class="artcardd flexRow">
												<a class="aritcle_card_img" rel="nofollow" href="/xiazai/skill10984" title="git提交前检查"><img
														src="https://img.php.cn/upload/skill/001/246/273/6adaf20d3191a227.jpg" alt="git提交前检查" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
												<div class="aritcle_card_info flexColumn">
													<a rel="nofollow" href="/xiazai/skill10984" title="git提交前检查" class="overflowclass">git提交前检查</a>
													<p class="overflowclass">在代码提交 git 前，通过 git diff 对比修改内容，逐文件审查变更点，检测潜在 BUG、隐含风险与可优化项，输出结构化审查报告。当用户表达提交前检查、提交检查、commit 前检查、pre-commit review、提前审查代码、检查一下改动、看看能不能提交等意图时使用此技能。注意：此技能与「代码评审」不同——代码评审在开发完成后结合需求文档与概要设计进行完整度审查，提交前检查是轻量级的基于 git diff 的代码质量把关。</p>
												</div>
												<a rel="nofollow" href="/xiazai/skill10984" title="git提交前检查" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
												</a>
											</div>
										</div>
<ul>
<li>当前最高位 1 等于 N 的最高位 1。</li>
<li>问题转化为计算 N 的剩余部分 "12" 的数位和计数，最大数位和为 5 - 1 = 4。即 DS(4, "12")。</li>
</ul>
</li>
</ul>
<p>所以，DS(5, "112") = DS(5, "99") + DS(4, "12")。</p>
</li>
<li>
<p><strong>计算 DS(5, "99")</strong>：</p>
<ul>
<li>N = "99"，最高位 D = 9。</li>
<li>遍历可能的最高位 d 从 0 到 min(5, 9)，即 0 到 5。</li>
<li>对于每个 d (从 0 到 5)，由于 d </li>
<li>DS(5, "99") = DS(5, "9") + DS(4, "9") + DS(3, "9") + DS(2, "9") + DS(1, "9") + DS(0, "9")。</li>
</ul>
</li>
<li>
<p><strong>计算 DS(max_s', "9")</strong> (一位数的情况，这是递归的基线条件)：</p>
<ul>
<li>对于一位数 N = "9"，其最高位 D = 9。</li>
<li>遍历可能的最高位 d 从 0 到 min(max_s', 9)。</li>
<li>对于每个 d，由于 d </li>
<li>实际上，对于 DS(max_s', "9")，我们可以直接计算：d 可以取 0, 1, ..., min(max_s', 9)。所以结果就是 min(max_s', 9) + 1。<ul>
<li>DS(5, "9") = min(5, 9) + 1 = 5 + 1 = 6 (数字 0, 1, 2, 3, 4, 5 的数位和都 </li>
<li>DS(4, "9") = min(4, 9) + 1 = 4 + 1 = 5</li>
<li>DS(3, "9") = min(3, 9) + 1 = 3 + 1 = 4</li>
<li>DS(2, "9") = min(2, 9) + 1 = 2 + 1 = 3</li>
<li>DS(1, "9") = min(1, 9) + 1 = 1 + 1 = 2</li>
<li>DS(0, "9") = min(0, 9) + 1 = 0 + 1 = 1</li>
</ul>
</li>
</ul>
<p>所以，DS(5, "99") = 6 + 5 + 4 + 3 + 2 + 1 = 21。</p>
</li>
<li>
<p><strong>计算 DS(4, "12")</strong>：</p>
<ul>
<li><p>N = "12"，最高位 D = 1。</p></li>
<li><p>遍历可能的最高位 d 从 0 到 min(4, 1)，即 0 到 1。</p></li>
<li>
<p><strong>当 d = 0 时</strong>：</p>
<ul>
<li>当前最高位 0 小于 N 的最高位 1。</li>
<li>问题转化为计算一个一位数（9）的数位和计数，最大数位和为 4 - 0 = 4。即 DS(4, "9")。</li>
<li>我们已经知道 DS(4, "9") = 5。</li>
</ul>
</li>
<li>
<p><strong>当 d = 1 时</strong>：</p>
<ul>
<li>当前最高位 1 等于 N 的最高位 1。</li>
<li>问题转化为计算 N 的剩余部分 "2" 的数位和计数，最大数位和为 4 - 1 = 3。即 DS(3, "2")。</li>
</ul>
</li>
</ul>
<p>所以，DS(4, "12") = DS(4, "9") + DS(3, "2") = 5 + DS(3, "2")。</p>
</li>
<li>
<p><strong>计算 DS(3, "2")</strong> (一位数的情况)：</p>
<ul>
<li>N = "2"，最高位 D = 2。</li>
<li>遍历可能的最高位 d 从 0 到 min(3, 2)，即 0 到 2。</li>
<li>DS(3, "2") = DS(3-0, "") + DS(3-1, "") + DS(3-2, "")</li>
<li>对于一位数 N = "2"，d 可以取 0, 1, 2。</li>
<li>DS(3, "2") = min(3, int("2")) + 1 = 2 + 1 = 3 (数字 0, 1, 2 的数位和都 </li>
</ul>
<p>所以，DS(4, "12") = 5 + 3 = 8。</p>
</li>
</ol><p>最终结果：DS(5, "112") = DS(5, "99") + DS(4, "12") = 21 + 8 = 29。</p><h3>记忆化搜索的重要性</h3><p>在上述递归过程中，我们可以看到像 DS(4, "9") 这样的子问题会被多次计算。为了避免重复计算，我们使用一个缓存（cache 或 memo）来存储已经计算过的状态的结果。当需要计算某个状态时，首先检查缓存；如果已存在，则直接返回；否则，计算并存储结果。这正是动态规划的核心思想之一。</p><h2>Python实现</h2><p>下面是基于上述数位DP思想的Python实现。</p><pre class="brush:php;toolbar:false;">def count_digit_sums_up_to_x(n_str, x, cache):
    """
    计算在字符串表示的数字 n_str 范围内（从0到n_str），
    数位和小于等于 x 的整数数量。

    参数:
        n_str (str): 表示上限数字的字符串。
        x (int): 允许的最大数位和。
        cache (dict): 用于存储已计算状态的记忆化字典。
                      键为 (n_str, x)，值为对应的计数。

    返回:
        int: 满足条件的整数数量。
    """

    # 基线条件：如果 n_str 只有一个数字
    if len(n_str) == 1:
        # 考虑从0到该数字的所有整数。
        # 例如，n_str="5", x=3，则数字可以是0,1,2,3，共4个。
        # 它们的数位和都小于等于3。
        # 但如果 x=0, n_str="5"，则只有数字0满足，共1个。
        # 所以是 min(x, int(n_str[0])) + 1
        return min(x, int(n_str[0])) + 1

    # 检查缓存
    if (n_str, x) in cache:
        return cache[(n_str, x)]

    # 获取当前数字的最高位
    top_digit = int(n_str[0])

    # 构建一个与 n_str 长度相同但除最高位外全为9的字符串，
    # 用于处理当前位小于 top_digit 的情况
    nines_suffix = '9' * (len(n_str) - 1)

    current_count = 0
    # 遍历当前位可能的数字 d
    # d 的范围是从 0 到 min(x, top_digit)
    for d in range(min(x, top_digit) + 1):
        if d <h3>代码解析</h3><ol>
<li>
<strong>count_digit_sums_up_to_x(n_str, x, cache) 函数</strong>：<ul>
<li>n_str：当前要处理的数字上限，以字符串形式传入，方便逐位操作。</li>
<li>x：当前允许的剩余最大数位和。</li>
<li>cache：一个字典，用于存储 (n_str, x) 状态的计算结果，实现记忆化。</li>
</ul>
</li>
<li>
<strong>基线条件 if len(n_str) == 1:</strong>：<ul>
<li>当 n_str 只剩一位时（例如 "5"），表示我们正在计算个位数。</li>
<li>结果是 min(x, int(n_str[0])) + 1。这表示从 0 到 min(x, n_str[0]) 的所有数字都满足条件。例如，如果 n_str="5", x=3，那么 0, 1, 2, 3 这四个数字的数位和都小于等于3，且它们都小于等于5。</li>
</ul>
</li>
<li>
<strong>记忆化 if (n_str, x) in cache:</strong>：<ul><li>在每次递归调用前，检查当前状态 (n_str, x) 是否已在缓存中。如果存在，直接返回缓存结果，避免重复计算。</li></ul>
</li>
<li>
<strong>循环 for d in range(min(x, top_digit) + 1):</strong>：<ul>
<li>top_digit 是 n_str 的当前最高位。</li>
<li>d 遍历当前位可以放置的数字。d 的上限是 top_digit（因为不能超过 n_str 的限制），同时也不能超过剩余允许的最大数位和 x。所以 d 的取值范围是 0 到 min(x, top_digit)。</li>
</ul>
</li>
<li>
<strong>递归调用</strong>：<ul>
<li><strong>d ：当前位 d 小于 n_str 的最高位。这意味着后续的位可以自由选择 0-9。因此，我们递归调用 count_digit_sums_up_to_x，将 n_str 的剩余部分替换为一个由 len(n_str) - 1 个 9 组成的全9字符串（nines_suffix），并更新剩余数位和为 x - d。</strong></li>
<li>
<strong>d == top_digit</strong>：当前位 d 等于 n_str 的最高位。这意味着后续的位仍然受到 n_str 剩余部分的限制。因此，我们递归调用 count_digit_sums_up_to_x，传入 n_str[1:]（n_str 的剩余部分），并更新剩余数位和为 x - d。</li>
</ul>
</li>
<li>
<strong>cache[(n_str, x)] = current_count</strong>：<ul><li>在所有子问题计算完毕并累加到 current_count 后，将结果存入缓存。</li></ul>
</li>
</ol><h2>复杂度分析</h2>

状态数量：n_str 的长度最多为 log10(N) (对于 N=10^12，长度约为 13)。x 的最大值对于 N=10^12，最大数位和为 9 * 12 = 108。因此，状态数量大约是 log10(N) * X。
每个状态的计算：在一个状态中，循环 d 的次数最多为 10 次（从 0 到 9）。每次循环都是一次递归调用或简单的加法。
总时间复杂度：O(log10(N) * X * 10)，可以简化为 O(log10(N) * X)。
- 对于 N=10^12 (约13位)，X=108：13 * 108 * 10 约为 14040 次操作。这相比于 10^12 次

Python免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 Python 的核心概念和高级技巧！