C語言數位DP入門：避開「62」與「4」的不吉利數字計數

問題描述

統計區間 [n, m] 中不包含數位 4 和連續數位 62 的整數個數。0 < n,m < 1,000,000。多組測試至 EOF。

原始代碼：暴力逐數檢查

對區間每個數，逐位檢查是否含 4 或 62。複雜度 O((m-n)×log m)，m-n≈10⁶ 時約 10⁷ 操作，勉強通過但非最優。

優化方案：數位動態規劃

定義 dp[pos][prev6][tight]：處理到第 pos 位（從高到低），前一位是否為 6，是否受上界限制的合法數字數。遞歸轉移枚舉當前位 0-9，跳過 4 和 prev6&&cur==2。時間 O(位數×2×2×10) ≈ O(1) 每查詢。

數位DP 實現代碼

#include <stdio.h>
#include <string.h>

int digits[10];
int dp[10][2][2]; // pos, prev6, tight
bool vis[10][2][2];

int dfs(int pos, bool prev6, bool tight) {
    if (pos == -1) return 1;
    if (!tight && vis[pos][prev6][0]) return dp[pos][prev6][0];
    int limit = tight ? digits[pos] : 9;
    int ans = 0;
    for (int d = 0; d <= limit; d++) {
        if (d == 4) continue;
        if (prev6 && d == 2) continue;
        ans += dfs(pos-1, d==6, tight && d==limit);
    }
    if (!tight) { vis[pos][prev6][0]=true; dp[pos][prev6][0]=ans; }
    return ans;
}

int count_lucky(int x) {
    if (x < 0) return 0;
    int len = 0;
    while (x) { digits[len++] = x%10; x/=10; }
    if (len==0) { digits[0]=0; len=1; }
    memset(vis, 0, sizeof(vis));
    return dfs(len-1, false, true);
}

int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) == 2) {
        if (n > m) { int t=n; n=m; m=t; }
        printf("%d\n", count_lucky(m) - count_lucky(n-1));
    }
    return 0;
}

關鍵優化效果

• 單次查詢 O(1)（位數固定 7 位），總複雜度 O(T) 而非 O(T×區間長度)。
• 支援極大範圍（如 10¹⁸）只需增加位數陣列大小。
• 記憶化搜索避免重複子問題計算。

狀態定義細節

• prev6：標記高位是否為 6，用於檢測「62」模式。
• tight：標記前綴是否已達上界，決定當前位上限。
• 前導零處理：prev6 在前導零階段保持 false，不觸發「62」誤判。

擴展：任意禁忌模式（AC 自動機 + 數位DP）

若禁忌模式為多個字串（如 "4", "62", "13"），可構建 AC 自動機，狀態為自動機節點，轉移為字符轉移，終止狀態為匹配到任一模式。複雜度 O(位數×節點數×10)。