算法解題：在 1 ~ N 之間，含有子字串 '14' 的整數有幾個？

Facebook LinkedIn Tweet

更新日期： 2025 年 3 月 7 日

題目要我們計算「在 1 ~ N 之間，含有子字串 ’14’ 的整數有幾個？」。

直接把所有數字轉成字串檢查，當 N 大到 10^10 時，時間必然不可行。

一個常見的技巧是：

先算不包含 ’14’ 的個數，記作 countNo14（N）。
再用總數 NN 去扣掉它： countWith14（N） = N − countNo14（N）（若題目範圍是 1 ∼ N,記得排除0）

因此核心問題是：如何快速算出 1 ∼ N1（或 0 ∼N ）之間「不含 ’14’」的數字個數？ 這裡就能利用「數位 DP」的手法來做。

數位 DP（Digit DP）應用方式

數位 DP 是一種用於計算在某個數字範圍內，滿足特定條件的數字個數的技巧。

它通過將數字逐位拆分，並應用動態規劃（DP）的方法來避免重複計算，從而實現高效的計算過程。

把上限 N 轉換成「位數陣列」

假設上限數字 N = 1234，我們將 N 轉換為位數陣列：

digits = [1, 2, 3, 4]

這個位數陣列表示從最高位到最低位的每個數字。
這樣做的好處是，我們可以在遞迴過程中方便地逐位處理數字，並且能夠清晰地判斷當前是否已經進入「自由模式」。

定義數位 DP 的遞迴函式 `dp(pos, prevDigit, isTight)`

1️⃣ 參數的含義

pos（位置）：表示當前正在處理數字的第幾位，從 0 開始計數，對應 digits 陣列的索引。
prevDigit（上一位數字）：用於記錄前一位填入的數字，幫助判斷當前位數字與前一位的組合，例如「14」的情況。
isTight（是否受上限約束）：表示當前位數是否仍受限於上限 N 的對應位數。
- isTight = 1：當前位數的選擇受到上限的限制，不能超過對應位數字。
- isTight = 0：當前位數可以自由選擇 0 ~ 9，因為之前的選擇已經讓當前數字小於上限 N。

DP 遞迴邏輯：每一位數字的選擇

1️⃣ 選擇當前位數 (`digit`) 的範圍

計算可選範圍

如果 isTight = 1（小心模式），可選數字是 0 到「當前位數的上限」。
如果 isTight = 0（自由模式），可選數字是 0 到 9。

maxDigit = digits[pos] if isTight else 9

2️⃣ 處理每個可能的 `digit` 選擇

在 for digit in range(0, maxDigit + 1) 中，逐一嘗試每個數字：

檢查是否觸犯「不能包含 ’14’」的條件

如果 prevDigit = 1 且當前選擇 digit = 4，則會構成子字串 "14"：
- 這條路徑不符合題目要求，直接跳過，不進行遞迴計算。

if prevDigit == 1 and digit == 4:
    continue  # 直接跳過這個選擇

計算下一個狀態的參數

下一位 (pos + 1)：處理下一個數字位。
新模式 (newTight)：根據當前選擇，判斷是否保持小心模式：
- 如果當前 isTight = 1，且 digit < maxDigit，則進入自由模式：newTight = 0。
- 否則，保持當前模式：newTight = isTight。

newTight = isTight and (digit == maxDigit)

遞迴計算並累加結果

把「下一層」對應的狀態計算出來，並累加到當前結果中：

result += dp(pos + 1, digit, newTight)

記憶化（Memoization）：避免重複計算

1️⃣ 狀態的記錄方式

在 DP 表中，記錄每個 (pos, prevDigit, isTight) 狀態的計算結果：

dp[pos][prevDigit][isTight] = result

2️⃣ 查表加速計算

每次進入 dp 函式時，先查看當前狀態是否已經計算過：

if dp[pos][prevDigit][isTight] != -1:
    return dp[pos][prevDigit][isTight]

如果已經有結果，直接返回，避免重複計算。

計算範圍和效率分析

1️⃣ 狀態數量估算

位數最大約 10 位 (pos = 0 ~ 9)。
前一位數字 (prevDigit) 有 0 ~ 9 共 10 種選擇。
isTight 只有 0 和 1 兩種情況。
因此，總狀態數約為 10 × 10 × 2 = 200，每個狀態再遍歷 0 ~ 9，總計最多約 2000 次操作，這對於 Python 來說是極快的。

最終結果計算方法

1️⃣ 計算「沒有 ’14’ 的數字總數」

countNo14(0..N)

表示從 0 到 N 之間，不含「14」 的數字個數。

2️⃣ 處理邊界情況：剔除 0 的影響

如果要計算「從 1 到 N」之間不含「14」的數字個數：

countNo14(1..N) = countNo14(0..N) - 1

減 1 是因為 countNo14(0..N) 包含了 0，但我們只需要 1 ~ N 的範圍。

3️⃣ 計算「含有 ’14’ 的數字個數」

countWith14 = N + 1 - countNo14(0..N)

這個公式的推導邏輯是：總數字個數（N + 1，因為包含 0 到 N）減去不含「14」 的數字個數，就是含有「14」 的數字個數。

程式範例

以下給出一個可以直接執行的 Python 範例。它包含：

count_no14_up_to(N)：回傳「從 0 到 N 之間，不含 ’14’ 的數字個數」的函式。
count_with14_in_1_to(N)：回傳「從 1 到 N 之間，包含 ’14’ 的數字個數」。

請注意：

為了好實作，我們在 DP 中直接算 0∼N0 \sim N 的不含 ’14’，然後最後做一點調整就能拿到答案。
你可以用它來算 N=10,000N = 10,000、10,000,00010,000,000、10,000,000,00010,000,000,000 等等。

def count_no14_up_to(N: int) -> int:
    """
    回傳從 0 到 N 之間，不含 '14' 的整數個數
    """

    digits = list(map(int, str(N)))  # 轉成位數
    n_len = len(digits)
    
    # dp(pos, prev, is_tight) 記憶化表
    # -1 代表還沒計算
    # dp 會回傳：從第 pos 位處理到末位，
    #           不會產生 '14' 的 valid 數量
    # prev = 前一位的 digit (若沒有上一位，給 -1 做為 "無意義" 狀態)
    from functools import lru_cache

    @lru_cache(None)
    def dfs(pos: int, prev: int, is_tight: bool) -> int:
        # pos 走到頭，表示一個完整數字產生，且還沒遇到 '14'
        if pos == n_len:
            return 1

        limit = digits[pos] if is_tight else 9
        total_count = 0

        for dig in range(limit + 1):
            # 假如上一位是 1，這一位 dig 是 4，代表出現 '14' → 這路徑直接跳過
            if prev == 1 and dig == 4:
                continue

            # 下一位是否還 tight，需看本位是否用到 limit
            next_tight = is_tight and (dig == limit)

            total_count += dfs(pos + 1, dig, next_tight)

        return total_count

    return dfs(0, -1, True)

def count_with14_in_1_to(N: int) -> int:
    """
    回傳從 1 到 N 之間，包含 '14' 的數字個數
    """
    if N <= 0:
        return 0
    # 從 0..N 之間不含 '14' 的個數
    no14_count = count_no14_up_to(N)
    # 從 1..N 含 '14' 的個數 = N + 1 - 不含 '14'（因為包含 0）
    return (N + 1) - no14_count

# ----------------------------------
# 以下示範計算題目需求
# ----------------------------------

# 1) 從 1 ~ 10,000 含 '14' 有多少?
ans1 = count_with14_in_1_to(10_000)
print("1 ~ 10,000 含 '14' 的個數 =", ans1)

# 2) 從 1 ~ 10,000,000 含 '14' 有多少?
ans2 = count_with14_in_1_to(10_000_000)
print("1 ~ 10,000,000 含 '14' 的個數 =", ans2)

# 3) 從 1 ~ 10,000,000,000 含 '14' 有多少?
ans3 = count_with14_in_1_to(10_000_000_000)
print("1 ~ 10,000,000,000 含 '14' 的個數 =", ans3)

時間複雜度簡析

整個 DP 的狀態 (pos, prev, is_tight) 最多約為「位數（10 或 11） × (前一位可能值 0~9 加上 -1) × 2」，大約二三百個。
每個狀態需要迴圈最多 10 次 (for dig in 0..9)。
總計數千次至數萬次呼叫以內，Python 在正常環境中可以非常快地處理（通常在 1 秒內就能跑完）。

因此即使要算到 101010^{10} 也沒問題，執行時間遠低於 2 秒。

範例：N = 14

我們以 count_no14_up_to(14) 這個呼叫為例，來追蹤整個遞迴流程。

上限 N = 14
- 轉成位數陣列 digits = [1, 4]
- n_len = 2 表示有兩位數 (pos = 0 / 1；到 pos=2 就表示完成)
主呼叫dfs( pos=0, prev=-1, is_tight=True )
- 這代表「目前在第 0 層樓」，prev=-1 表示「上一層不存在」，is_tight=True 表示「還受最嚴格的限制（跟著 N）」。

第 1 層呼叫：dfs(0, -1, True)

pos = 0
prev = -1（上一層不存在）
is_tight = True
因為 is_tight=True，所以 limit = digits[0] = 1
→ 本層（pos=0）只能選擇 dig 在 [0..1] 之間

1️⃣ 迴圈： `for dig in range(0, limit+1)` = `for dig in [0, 1]`

(1) `dig = 0`

檢查「前一位 = 1、這一位 = 4」的危險組合？
- 這裡 prev=-1，不符合 (1,4) → 不跳過
next_tight = is_tight and (dig == limit) → True and (0 == 1) → False
呼叫：

dfs( pos=1, prev=0, is_tight=False )

等這個呼叫回傳後，加到 total_count。

(2) `dig = 1`

同樣檢查「(1,4)」？
- 前一位 = -1，不是 1 → 不跳過
next_tight = True and (1 == 1) → True
呼叫：

dfs( pos=1, prev=1, is_tight=True )

最後會將兩次呼叫回傳的值相加，得到 dfs(0, -1, True) 的最終 total_count。

第 2 層呼叫 A：dfs(1, 0, False)

pos = 1
prev = 0
is_tight = False → 代表「已經比上限小」，所以後續可以自由選擇 0~9
limit = 9（因為不再受嚴格限制）

1️⃣ 迴圈： `for dig in [0..9]`

對於 dig = 0,1,2,3,4,5,6,7,8,9：

檢查 (prev=1 and dig=4)？現在 prev=0，所以不會跳過。
next_tight = False and (dig == 9)? → 永遠是 False，因為 False and anything = False
呼叫 dfs( pos=2, prev=dig, is_tight=False )

2️⃣ pos=2 代表「已巡視到超過末位」

在程式中，if pos == n_len: return 1
所以每個呼叫都直接回傳 1。

因此這裡總共有 10 種 dig（0~9），每種都回傳 1，合計 10。

→ dfs(1, 0, False) 回傳 10。

第 2 層呼叫 B：dfs(1, 1, True)

pos = 1
prev = 1
is_tight = True
limit = digits[1] = 4（因為還在跟 N=14 的第 1 位數同步）

1️⃣ 迴圈： `for dig in [0..4]`

各 dig 分析

dig = 0
- 檢查 (prev=1 and dig=4)? → (1,0)? 不符 → 不跳過
- next_tight = True and (0 == 4)? → False
- 呼叫 dfs(2, 0, False) → 回傳 1
- 累計 total_count = 1
dig = 1
- (1,1)? 不跳過
- next_tight = True and (1 == 4)? → False
- dfs(2, 1, False) → 回傳 1
- total_count = 2
dig = 2
- (1,2)? 不跳過
- next_tight = False
- dfs(2, 2, False) = 1
- total_count = 3
dig = 3
- (1,3)? 不跳過
- next_tight = False
- dfs(2, 3, False) = 1
- total_count = 4
dig = 4
- 檢查 (prev=1 and dig=4)? → 是 (1,4)，跳過！
- 直接 continue，不遞迴也不增加 total_count。

結果

累計 total_count = 4
因此 dfs(1, 1, True) 回傳 4。

回到第 1 層呼叫

我們把兩條分支（A 與 B）的結果相加：

dig=0 時呼叫 => dfs(1, 0, False) => 回傳 10
dig=1 時呼叫 => dfs(1, 1, True) => 回傳 4

所以：

total_count = 10 + 4 = 14
dfs(0, -1, True) 回傳 14

最終結果： count_no14_up_to(14) = 14

檢驗：0~14 共有 15 個數字 (0,1,2,…,14)

唯一含有 “14” 的就是 14 這個數字本身
所以不含 “14” 的數字共有 14 個
與遞迴結果 14 完全一致。

如果我們要算「1~14 含 ’14’ 的數量」，則會用： (14+1)−14=1,(14 + 1) – 14 = 1,

對應到只有一個數字 14 含有 “14”。

路徑在程式中的意義

在這類 Digit DP 的程式裡，我們通常會寫一個遞迴函式（例如 dfs(pos, prev, is_tight)），然後在裡面用 for dig in range(...) 的迴圈，去嘗試每一個可能的下一位數字。

每一層都可能有多條分支，而每條分支都會繼續往下（呼叫下一層）直到結束。

你可以想像：「一個數字有多少位，就有幾層樓，每層要選哪個數字，就像每層樓要開多少房間。每一層的一次選擇，就把你帶去下一層繼續做決定。」
一路從最上層（pos = 0）選到最末層（pos = n_len），就得到一條「完整的路徑」——也就是「一個具體的整數（它每一位數字是什麼）」。

所以，在遞迴或樹狀結構的描述中，我們把「從根節點走到葉節點」的這條走法，稱之為一條「路徑」。

為什麼要「避開」含 ’14’ 的路徑

在我們想算「不含 ’14’」的數字時：

每條路徑都代表「可能構成的一個數字」。
若這條路徑中某兩層（相鄰位）選到 (1,4)，就代表這個數字含有 ’14’。
「避開含 ’14’ 的路徑」意思就是：只要在某層偵測到「上一位 = 1、現在位 = 4」，就不再繼續下去（也不把這條路徑計入）——這就等於把「含 ’14’」的數字直接排除。

在程式層面就是這一行程式碼：

if prev == 1 and dig == 4:
    continue  # 直接跳過這條分支

這表示：如果上一位選的數字是 1，而本位正要選 4，會形成 “14”，我們就不往下遞迴、也不把它算進總數。

總結

「路徑」：指的是遞迴（或樹）中，從起點一路走到終點、每層做一次選擇的「完整走法」。
在計算「不含 ’14’」的作法裡，我們在每一步偵測到 (1,4) 就不繼續下去，相當於把「含 ’14’」的那條路徑避開，只留下不會形成 “14” 的路徑。
最後統計這些剩下的路徑數量，就得到「不含 ’14’」的數字有多少，再用總數減一減，就能得到「含 ’14’」的個數。