数位DP优化：避免62与4的吉利数计数

数位动态规划（Dynamic Programming on Digits, 数位DP）在计算机科学中是一种高效的算法技巧，尤其适用于那些具有重复子问题且可以利用子问题结果进行优化的问题。本篇分享着重于一种名为“某次队内分享任务”的数位DP实践，以解决特定的计算问题。 在讲解开始时，作者通过实例介绍了如何利用朴素算法来解决一个吉利数计数问题。在HDU-2089问题中，我们需要计算从n到m（1 <= n <= m <= 1e6）之间的吉利数数量，其中不吉利的数包含数字4或62。朴素算法首先预处理1到1e6的所有数，判断是否吉利，然后用前缀和的方法快速查询区间内的吉利数个数。 原始算法的时间复杂度是O(n * k)，其中n是数的范围，k是每位数的判断复杂度（在这里为O(1)）。然而，数位DP提供了一种更高效的方法。它通过将数视为一棵树，每个数字对应一个节点，树的深度表示数字的位数，而从超级源点（根节点）到叶子节点的路径代表了所有可能的数。关键在于，数位DP允许我们识别并利用重复的路径计数，从而减少不必要的计算。 优化思路如下： 1. **构建树结构**：将数视为一棵深度优先搜索（DFS）的树，根节点代表整个数，子节点代表每一位数字，深度表示位序。例如，对于数7575023，每个数字的位置和对应的值形成数组a。 2. **状态转移**：通过递归或迭代的方式，数位DP中的状态通常表示从超级源点到当前位置的路径数，这些路径数会随着深度变化。在本例中，我们关注的是不含4或62的路径数。 3. **状态合并**：在朴素方法中，树的大小为n（数的最大位数），但通过观察，许多节点的路径数是相同的，如所有个位数为3的数路径数都相同。通过合并这些具有相同路径数的节点，我们可以显著减少状态的数量，降低空间复杂度。 4. **时间复杂度优化**：通过状态压缩和重用已计算的结果，我们可以将时间复杂度从O(n * k)降低到O(n + m)，甚至更低，极大地提高了算法效率。 总结来说，数位DP在处理这类涉及数字组合的计数问题时，通过巧妙地构造状态和利用子问题的重复性，能够大幅度提升算法性能。在实际编程中，理解和应用数位DP的关键在于理解问题的状态转移规则以及如何有效地合并或存储状态，以便在后续的计算中重复利用。