🔗 🔴 3966. Count Good Integers in a Range

Problem Statement

題目簡述

給定三個整數 ll、rr 和 kk。如果一個正整數的任意相鄰數位之間的絕對差值都不超過 kk，則稱該整數為「好數」。求區間 [l,r][l, r] 內好數的個數。

Constraints

約束條件

  • 10≤l≤r≤101510 \le l \le r \le 10^{15}
  • 0≤k≤90 \le k \le 9

思路：雙邊界限制數位 DP

「統計區間內符合某種數位條件的整數個數」是典型的數位 DP 問題。直接枚舉最多要檢查 101510^{15} 個數，顯然不可行；合理的做法是從高位到低位逐位填數字，並將重複的遞迴狀態記憶化。

本題的限制條件只和「前一個有效數位」有關——填入目前數位時，只要它和前一位的差值不超過 kk，就能繼續往後填。

雙邊界數位 DP

一般寫法是 f(r)−f(l−1)f(r) - f(l-1)。但本題實作採用另一種方式：把 ll 補前導零到與 rr 等長，然後在同一趟搜索中同時維護是否貼著下界、是否貼著上界。

遞迴過程需要記錄四個資訊：目前填到哪一位、前一個有效數位是多少、是否仍受下界限制、是否仍受上界限制。

每一位的可填範圍由邊界狀態決定：若還貼著下界，最小值不能低於 ll 的對應位；若還貼著上界，最大值不能高於 rr 的對應位。一旦脫離某個邊界，該方向後續就可以自由選填 0∼90 \sim 9。

前導零不能參與差值判斷

由於 ll 被補了前導零，在尚未填入真正數位之前，必須用一個特殊狀態表示「還沒有前一位」，以免第一個有效數位被前導零錯誤限制。

轉移時分兩種情況：

  • 若還在補齊長度的前導零區域，可以選擇繼續跳過該位，且前一位狀態保持為「尚未開始」。
  • 否則枚舉目前可填的數位，只要它是第一個有效數位，或與前一位的差值不超過 kk，就可以遞迴到下一層。

複雜度分析

  • 時間複雜度：O(D⋅Σ2)\mathcal{O}(D \cdot \Sigma^2)，其中 D=O(log⁡r)D = \mathcal{O}(\log r) 為 rr 的位數，Σ=10\Sigma = 10 為數位基數。狀態數為 D×Σ×2×2D \times \Sigma \times 2 \times 2，每個狀態最多枚舉 Σ\Sigma 個目前數位。
  • 空間複雜度：O(D⋅Σ)\mathcal{O}(D \cdot \Sigma)，即狀態數量。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def goodIntegers(self, l: int, r: int, k: int) -> int:
        n = len(str(r))
        diff = n - len(str(l))
        high = list(map(int, str(r)))
        low = list(map(int, str(l).zfill(n)))

        @cache
        def dfs(i: int, pre: int, limit_low: bool, limit_high: bool):
            if i == n:
                return 1

            lo = low[i] if limit_low else 0
            hi = high[i] if limit_high else 9

            res = 0
            if i < diff and limit_low:
                res += dfs(i + 1, -1, True, False)
            for d in range(1 if i < diff and limit_low else lo, hi + 1):
                if pre == -1 or abs(pre - d) <= k:
                    res += dfs(i + 1, d, limit_low and d == lo, limit_high and d == hi)
            return res

        ans = dfs(0, -1, True, True)
        dfs.cache_clear()
        return ans