數位是指數字位數，個人偏好講位數。DP是指動態規劃，一次參與進兩個，對於初學者肯定是相當難理解的。(我也花幾天去釐清思路到能用
動態規劃簡單的說法：就是用「空間換時間」，把問題拆成子問題作解決，子問題都常會被重複計算，像是費氏數列 fib(x) = fib(x-1) + fib(x-2)，用空間記住參數對應的答案，就能減少計算時間。
而數位DP的特徵就是會給予「界限 Bound」，例如在 0 ~ 99 區間找不含某種條件的數字總數等，像是不包含 5 的數字總數。
一旦看到這樣的敘述，就能夠準備開打數位DP的模板了。
先不講如何寫，這裡先講觀念。
dp = dict() #字典
dp[pos][stats][bound]，由三個部分組成，pos位數、stats統計、bound邊界。(※pos跟bound是固定的，stats可以超出一項。
像是”99″有兩位數，所以 pos = {0, 1} 分別對應 |9|9 跟 9|9| 的位數。
bound是邊界，狀態有四種。
0：無上下界
1：下界
2：上界
3：上下界
l, r為該位數的左右邊界，如果受下界影響， l 會是下界相同位數的數字；如果受上界影響，r 會是上界相同位數的數字。
如果區間是 09 到 21 間，首先搜尋函數會傳入 pos = 0, stats(暫不提), bound = 3。
在 [0] 位置，bound = 3 代表 l, r 受上下界 |0|9 與 |2|1 的影響，因此可選範圍在 {0, 1, 2}，可寫成 range(l, r+1)。
此時如果選 0，數字與下界符合，往深搜尋要傳入 (pos+1, nextStats, nextBound=1)，仍受下界限制。
此時如果選 1，數字不與上下界相同，往深搜尋要傳入 (pos+1, nextStats, nextBound=0)，代表下一位可選範圍是最自由的 0 – 9 。
選 2 的話，下一位會受上界影響。
關鍵點來了，stats 這個會受到題目限制而有所影響。
目前的題目是：在 09 到 21 區間內找 不含 “5” 個數。
要知道有沒有 “5” 的出現，我們可以用 “5” 去匹配，如果有匹配到，索引+1，然後直到索引到達自身長度就代表全匹配，即有 “5” 出現。
因為要找不含 “5” 的組合數，所以這裡的 pattern 便是 “5”。而 stats 起始條件是 0，代表從 pattern 位置 [0] 開始匹配。
因此 dp[0][0][3] 也代表題目所求且符合所有條件的個數，符合上下界條件跟搜索條件，而搜索條件會寫在搜尋函數。
如果當前組合位置符合 patter[i]，便 i+1 往下，下一位傳入的參數 (pos+1, i+1, bound)，於是下一位數所有枚舉會去匹配 patter[i+1] 。
要是pattern索引達到自身長度，代表當前組合含 “5”，沒有必要繼續往下搜尋，也不需要再枚舉， retrun 0。
符合題目要求的條件是pos到達自身長度，到達邊界時，仍沒有全匹配出現，此時 return 1，代表此組合符合題目要求。
"""
digit dynamic programming 入門
「在 [0-9] 區間內，找出 不含"5" 個數」
"""
# 在 [0-9] 區間內，找出 不含"5" 個數
s2 = "9"
s1 = "0"
p = "5"
# 建構 dp 表
dp = dict()
for pos in range(len(s2)):
dp[pos] = {}
for stats in range(len(p)):
dp[pos][stats] = {}
for bound in range(4):
dp[pos][stats][bound] = -1 # -1 代表尚未搜尋過
# 建構 搜尋函數 dfs深度優先搜尋(白話：從底找上來)
def dfs(pos, stats, bound):
# 回傳符合條件或不符合條件的值
# 如果模板索引為1，代表找到 "5"
if stats == len(p): return 0
# 找到底，且過程中沒有找到 "5"
if pos == len(s2): return 1
# 有被找過，則直接回傳值
if not dp[pos][stats][bound] == -1: return dp[pos][stats][bound]
"""
當前枚舉範圍設定
bound = 0: 無上下界
bound = 1: 只下界
bound = 2: 只上界
bound = 3: 上下界
"""
if bound == 1 or bound == 3:
l = int(s1[pos]) # ※要小心，s1是str，但l得是int
else:
l = 0
if bound == 2 or bound == 3:
r = int(s2[pos])
else:
r = 9
# 開始枚舉
result = 0
for num in range(l, r+1):
"""
後面的邊界會受前面的影響。
想想 (12, 16) 、 (09, 21) 後位取界的問題
在 (12, 16) 中，最高位都是 1，因此後位需要受上下界影響
在 (09, 21) 中，枚舉時最高位取 2，可以想成在枚舉(20, 21)，後位受上界影響。
在 (09, 21) 中，枚舉時最高位取 1，可以想成在枚舉(10, 19)，後位不受上下界影響。
在 (09, 21) 中，枚舉時最高位取 0，可以想成在枚舉(09, 09)，後位受下界影響。
"""
if bound == 3 and num == l and num == r:
nextBound = 3
elif (bound == 2 or bound == 3) and num == r:
nextBound = 2
elif (bound == 1 or bound == 3) and num == l:
nextBound = 1
else:
nextBound = 0
# 匹配：暴力匹配法(只適用pattern長度1，超過1請用KMP)。匹配結果影響放在函式前方
nextStats = stats + 1 if str(num) == p[stats] else 0
result += dfs(pos+1, nextStats, nextBound)
dp[pos][stats][bound] = result
return result
print(dfs(0, 0, 3)) # => 9
這裡的搜尋使用暴力匹配法，但只限於長度1，為什麼長度超過1不能使用？
在暴力匹配法在過程中匹配失敗，就會回到Target索引+1繼續從頭匹配。但是數位DP的索引是一路往深，若碰到11112、1112，會在 111|1|2、111|2| 位置上匹配失敗。若採用暴力匹配法，下一步應該是去匹配 1|1|112、|1|112，此時數位DP已經在pos[3]，很難回到pos[1]再重新匹配。(會花很多時間。)
所以要是使用KMP，就能夠不回溯Target的索引搜尋到底，相對也會順暢許多。