1. 從一個“簡單”的計數問題說起最近在帶新人刷算法題遇到一個經典問題它看起來人畜無害卻讓不少初學者栽了跟頭。題目大意是這樣的給你一個長度為n的格子你需要用k種顏色去涂滿它。但有一個限制相鄰的兩個格子不能涂成相同的顏色。問一共有多少種不同的涂色方案乍一看這不就是個排列組合題嗎第一個格子有k種選擇第二個格子不能和第一個相同所以有k-1種選擇以此類推?？偡桨笖挡痪褪莐 * (k-1)^(n-1)嗎這個公式在n和k都不大的時候確實能快速給出答案。很多新人做到這里就心滿意足地提交了然后……就收到了一個“Wrong Answer”。問題出在哪這個公式成立的前提是顏色是“無限”的或者說我們每次選擇時可用的顏色數量只受“上一個格子顏色”這一個條件的約束。但在很多實際問題中約束條件要復雜得多。比如如果顏色數量k很小或者題目增加了額外的限制比如“首尾格子也不能同色”甚至“某些特定位置的格子有固定顏色要求”剛才那個簡單的乘法原理就立刻失效了。這時我們面對的就不再是一個有閉合公式的問題而是一個需要系統化搜索所有可能狀態的問題。這就是“著色方案”類問題的核心在滿足一系列復雜約束條件下計算所有可行的分配方案總數。當約束變得具體而微暴力枚舉所有可能性在數據規模稍大時就會變得不可能時間復雜度是k^n的指數級。此時我們亟需一種更聰明的方法而“記憶化搜索”正是為此而生的利器。它不是什么高深莫測的黑魔法而是我們面對復雜狀態空間時一種化繁為簡、避免重復勞動的樸素思想。接下來我們就剝開這層外衣看看它到底是怎么工作的以及如何用它來優雅地解決那些看似棘手的計數問題。2. 暴力搜索的困境與狀態定義的藝術在討論記憶化搜索之前我們必須先理解它所試圖優化的對象——深度優先搜索DFS。對于著色問題最直接的思路就是遞歸回溯從第一個格子開始嘗試每一種可能的顏色如果當前選擇不違反約束比如和左邊格子顏色不同就遞歸地去涂下一個格子。當所有格子都涂滿時就得到了一種合法方案計數器加一。def dfs(position, n, k, prev_color): if position n: # 所有格子涂完找到一種方案 return 1 total 0 for color in range(k): if color ! prev_color: # 簡單相鄰約束 total dfs(position 1, n, k, color) return total # 初始調用假設第一個格子左邊沒有格子prev_color用-1表示 result dfs(0, n, k, -1)這段代碼清晰易懂但它有一個致命缺陷存在大量重復計算。舉個例子假設n5, k3。當我們遞歸探索時可能會先走顏色序列A-B-?這條路徑計算完后面所有的可能性。之后在另一條分支里我們可能又遇到了顏色序列C-B-?的狀態。注意此時雖然前兩個格子的顏色不同A和C但第二個格子都是B并且我們即將面對的是第三個格子。對于從“第三個格子開始前一個顏色是B”這個子問題它的答案是完全一樣的與第一個格子是A還是C無關然而我們的樸素DFS會傻乎乎地重新計算一遍。這就是狀態重疊。我們遞歸函數的本質是在計算一個(當前位置, 前一個格子顏色)所確定的子問題的解。一旦這個二元組(pos, prev_color)確定了無論通過哪條路徑到達這個狀態后續的涂色方案數都是唯一確定的。如果我們能把這個結果存起來下次再遇到相同的(pos, prev_color)時直接返回結果就能節省巨大的計算量。所以記憶化搜索的第一步也是最重要的一步就是精確定義“狀態”。狀態必須能唯一標識一個子問題并且其數量是可控的。對于基本的相鄰不同色問題狀態就是(pos, prev_color)。其中pos的范圍是0到nn表示已涂完是遞歸終點prev_color的范圍是k種顏色再加上一個表示“無前驅”的特殊值比如-1。因此狀態總數大約是(n1) * (k1)這是一個多項式級別遠遠小于指數級的k^n。注意狀態定義并非一成不變。如果約束變成“首尾不能同色”我們的狀態就需要增加信息比如變成(pos, prev_color, first_color)因為最后一個格子的選擇受第一個格子顏色的影響。定義狀態的關鍵在于找出哪些信息是決定后續選擇所必需的、最小的信息集合。這需要根據具體問題的約束條件進行設計和提煉是記憶化搜索中最具技巧性的部分。3. 記憶化搜索的實現框架與細節打磨理解了狀態實現記憶化搜索就水到渠成了。我們用一個緩存通常是一個字典或數組來存儲已經計算過的狀態結果。這個緩存結構的選擇很有講究。1. 緩存數據結構的選擇字典Dict/HashMap最通用和靈活。鍵Key是狀態值Value是結果。當狀態比較復雜比如包含多個離散變量時用字典很自然。例如狀態(pos, prev_color)可以轉化為元組(pos, prev_color)作為鍵。多維數組List/Array當狀態的所有維度都是整數且范圍明確時使用數組訪問效率更高。例如pos范圍[0, n]prev_color范圍[-1, k-1]我們可以建立一個(n1) x (k1)的二維數組dp其中dp[pos][prev_color1]存儲結果1是為了將-1映射到索引0。在著色方案這類典型問題中狀態維度固定且范圍小使用數組是更優解。它不僅速度快而且代碼清晰。2. 遞歸函數的改造我們將樸素的DFS函數改造成一個“有記憶”的DFS。第一步查緩存。在函數開始時先檢查當前狀態是否已經計算過。如果是直接返回緩存的結果。第二步遞歸計算。如果沒計算過則進行正常的遞歸邏輯計算所有可能的選擇并求和。第三步存緩存。在返回結果之前將(當前狀態, 計算結果)存入緩存。以下是使用二維數組作為緩存的經典實現def count_colorings(n, k): # dp[pos][prev_color1], 初始化所有值為-1表示未計算 # prev_color 從 -1 到 k-1所以第二維大小是 k1 dp [[-1] * (k 1) for _ in range(n 1)] def dfs(pos, prev_color_idx): # prev_color_idx 是 prev_color 在dp數組中的索引 (prev_color 1) if pos n: return 1 # 成功涂完所有格子找到一種方案 if dp[pos][prev_color_idx] ! -1: return dp[pos][prev_color_idx] total 0 for color in range(k): # 將顏色值color轉換為“前一個顏色”的索引表示用于比較 # 注意prev_color_idx 是索引真正的 prev_color prev_color_idx - 1 actual_prev_color prev_color_idx - 1 if color ! actual_prev_color: # 遞歸下一個位置的前一個顏色索引是 color 1 total dfs(pos 1, color 1) dp[pos][prev_color_idx] total return total # 初始調用從位置0開始前一個顏色不存在用索引0表示即 actual_prev_color -1 return dfs(0, 0) # 示例5個格子3種顏色相鄰不同色 print(count_colorings(5, 3)) # 輸出應為 3 * 2^4 48可以用公式驗證3. 邊界條件與初始化遞歸的終點pos n通常返回 1表示找到一種完整方案。緩存數組的初始化值必須是一個不會出現在正常結果中的值如-1用以區分“未計算”和“計算結果為0”后者在某些問題中是合法結果表示無解。4. 復雜度分析時間復雜度由于每個狀態(pos, prev_color)最多只計算一次每次計算需要遍歷k種顏色所以總時間復雜度為O(n * k * k)等等仔細看內層循環。對于每個狀態我們循環k次每次遞歸調用是 O(1) 的查表或計算。因此準確的時間復雜度是O(狀態數 * 每個狀態的計算成本) O(n * k * 1) O(n * k)。這里的k是顏色數通常是個常數或者不大的數因此算法是線性或近似線性的效率極高?？臻g復雜度主要是緩存數組dp的開銷為O(n * k)以及遞歸調用棧的深度O(n)。實操心得在實現時我強烈建議將“狀態”到“緩存索引”的映射關系單獨寫成一個清晰的函數或注釋。比如get_index(prev_color)。這能極大減少因為下標轉換錯誤導致的Bug尤其是在狀態變量有特殊值如-1的時候。另外對于結果可能非常大的計數問題比如方案數可能超過64位整數范圍要在題目要求下及時取模并且在存入緩存和返回結果前都要取模保證一致性。4. 從經典到變種應對更復雜的約束條件記憶化搜索的強大之處在于其靈活性。當問題的約束條件發生變化時我們通常不需要推翻重來而只需調整“狀態定義”和“狀態轉移”邏輯。下面我們通過幾個變種問題來體會這一點。4.1 變種一首尾格子也不能同色這是“相鄰不同色”問題的經典加強版。此時最后一個格子第n-1個的顏色不僅不能和它左邊的格子第n-2個相同還不能和第一個格子相同。狀態定義的升級原來的狀態(pos, prev_color)不足以決定最后一個格子的選擇因為它缺少了“第一個格子顏色”的信息。因此我們需要將“第一個格子的顏色”也納入狀態。定義狀態為(pos, prev_color, first_color)。其中first_color在遞歸開始時就確定下來并一路傳遞下去。狀態轉移的調整在遞歸涂色時當pos 0涂第一個格子遍歷所有k種顏色作為first_color同時這個顏色也是prev_color。當pos n-1涂最后一個格子遍歷顏色時除了要滿足color ! prev_color還必須滿足color ! first_color。其他位置和之前一樣只需滿足color ! prev_color。緩存維度狀態變成了三維(pos, prev_color, first_color)緩存數組的大小變為(n) * (k) * (k)。雖然空間變大了但相對于指數爆炸這依然是完全可以接受的。4.2 變種二顏色使用次數限制假設每種顏色最多只能使用m次。這在實際場景中很常見比如有限的顏料庫存。狀態定義的升級此時僅僅知道前一個顏色是什么不夠了我們還需要知道每種顏色還剩多少使用次數。一種直觀的狀態定義是(pos, prev_color, color_used_tuple)其中color_used_tuple是一個長度為k的元組記錄每種顏色已使用的次數。但這樣狀態空間會非常大n * k * (m1)^k。優化思路對于計數問題我們往往不需要知道每種顏色具體用了多少次而只需要知道“剩余使用次數”的模式。如果所有顏色的限制次數m相同那么問題可以簡化為在涂到某個位置時有多少種顏色已經用滿了m次有多少種顏色用了m-1次……但這依然復雜。一個更實用的方法是當k和m不大時可以使用狀態壓縮。用一個k位的整數比特位來表示哪些顏色已經用盡了次數或者用一個整數數組來記錄使用次數并將整個數組作為字典的鍵雖然效率會降低。這體現了記憶化搜索的另一個維度當狀態本身復雜時我們可以利用哈希表字典的靈活性來存儲。4.3 變種三格子分組著色圖著色問題的簡化問題升級為格子之間不是簡單的線性關系而是一個一般的圖。每個節點格子需要著色有邊相連的節點不能同色。這就是經典的圖著色問題是NP難的。但對于特定的、樹狀或稀疏的圖記憶化搜索結合樹形DP仍然可以高效解決。狀態定義對于樹形結構我們通常在樹上進行DFS。狀態可以定義為(node, parent_color)表示在以node為根的子樹中當node的父節點顏色為parent_color時該子樹的著色方案數。然后通過遞歸合并子節點的結果來計算當前節點的方案數。踩坑實錄在處理復雜約束時最容易犯的錯誤是狀態定義遺漏了關鍵信息。我曾在一個比賽中遇到一個問題要求“任意兩個距離為2的格子也不能同色”。我最初只定義了(pos, prev_color)結果總是少算。后來才意識到距離為2意味著當前格子不能和它前面第2個格子同色。因此狀態必須包含前兩個格子的顏色信息即(pos, color_of_pos_minus_1, color_of_pos_minus_2)。這個教訓讓我明白定義狀態時要像偵探一樣問自己“要唯一確定從現在開始的所有未來可能性最少需要知道過去的哪些信息”5. 記憶化搜索 vs. 動態規劃思維路徑的異同很多人會把記憶化搜索和動態規劃DP等同起來稱其為“遞歸形式的DP”。這種說法有一定道理但兩者在思維起點和實現方式上有著微妙的區別理解這些區別能幫助你更好地選擇工具。5.1 思維路徑的對比記憶化搜索Memoization思維是自頂向下的。你從要解決的原問題如f(0, -1)開始思考“要解決我的問題我需要先解決哪些子問題”然后遞歸地去解決這些子問題并用緩存避免重復。它的思路更符合人類面對復雜問題的自然分解過程——分而治之。動態規劃Dynamic Programming思維是自底向上的。你需要先確定所有子問題的計算順序通常是較小的、基礎的狀態先計算然后通過迭代循環從小問題逐步推導出大問題的解。這需要更強的“全局”狀態轉移視角。對于著色方案問題記憶化搜索的思維是“我想知道從第0個格子開始涂有幾種方案。那我先試試涂第一種顏色然后問題就變成了‘從第1個格子開始且前一個顏色是第一種顏色’有幾種方案。我去計算這個子問題……”而動態規劃則會先計算“最后一個格子怎么涂”然后倒推回來或者從第一個格子開始正推。5.2 實現形式的對比我們以基礎著色問題為例看看兩者的代碼實現。記憶化搜索遞歸如上文所示代碼直觀反映了遞歸關系。動態規劃迭代我們需要定義dp[i][c]表示“涂完前i個格子并且第i個格子最后一個顏色是c的方案總數”。狀態轉移dp[i][c] sum(dp[i-1][c])其中c是所有不等于c的顏色。因為第i個格子涂c那么第i-1個格子可以是任何非c的顏色。初始化dp[0][c] 1對于第一個格子每種顏色都是一種方案。最終答案sum(dp[n-1][c])對所有顏色c求和。def count_colorings_dp(n, k): if n 0: return 0 # dp[i][c]: 前i個格子已涂完且第i個格子顏色為c的方案數 (i從0開始) dp [[0] * k for _ in range(n)] # 初始化第一個格子 for c in range(k): dp[0][c] 1 # 遞推 for i in range(1, n): for c in range(k): # 當前格子涂c上一個格子可以涂任何非c的顏色 for prev_c in range(k): if prev_c ! c: dp[i][c] dp[i-1][prev_c] # 總和 total sum(dp[n-1][c] for c in range(k)) return total5.3 如何選擇優先考慮記憶化搜索當狀態轉移關系不那么直觀或者存在復雜的依賴關系比如在樹上記憶化搜索更容易思考和實現。你只需要寫出遞歸關系讓緩存去處理重復子問題?？紤]動態規劃當問題有明顯的線性順序且狀態轉移方程清晰簡單時DP的迭代形式通常效率稍高避免了遞歸調用開銷并且不容易出現棧溢出對于深度很大的遞歸。一個實用的建議先嘗試用記憶化搜索的思路去思考和解決問題。寫出遞歸函數。如果發現性能或棧深度有問題再考慮是否能轉化為等價的、自底向上的動態規劃。很多時候記憶化搜索是探索DP狀態轉移方程的絕佳跳板。個人經驗在競賽或面試中如果時間緊迫我通常會首選記憶化搜索。因為它更不容易出錯思維負擔小。只要確保狀態定義正確、緩存生效基本就能拿到分數。而自底向上的DP一旦遞推順序或初始化寫錯調試起來可能更費時間。當然對于狀態空間巨大、需要滾動數組優化空間的情況就必須使用迭代DP了。6. 性能優化與邊界陷阱即使使用了記憶化搜索如果不注意細節依然可能掉入性能或正確性的陷阱。這里分享幾個關鍵點。6.1 緩存鍵的設計與哈希效率當使用字典Python的dict或functools.lru_cache時狀態的哈希效率至關重要。最常用的方法是將狀態轉換為元組Tuple。但要注意如果狀態中包含列表List必須先轉換為元組因為列表是不可哈希的。對于整數狀態直接使用元組即可。對于復雜對象可以考慮使用字符串編碼或自定義哈希函數。在Python中使用lru_cache(maxsizeNone)裝飾器可以極簡地實現記憶化它自動將函數參數作為緩存鍵。這對于原型設計和快速驗證非常方便。from functools import lru_cache lru_cache(maxsizeNone) def dfs(pos, prev_color): if pos n: return 1 total 0 for color in range(k): if color ! prev_color: total dfs(pos 1, color) return total6.2 遞歸深度限制Python默認的遞歸深度限制通常為1000對于n較大的問題可能不夠。對于線性遞歸深度為n的問題當n超過1000時需要手動設置遞歸深度或改用迭代DP。import sys sys.setrecursionlimit(10000) # 設置為一個更大的值但更根本的解決方法是評估問題是否必須深度遞歸。像著色方案這種問題遞歸深度等于格子數n如果n達到10^5級別即使解除限制遞歸調用棧的開銷也極大且有棧溢出風險。此時必須使用迭代的動態規劃。6.3 大數取模的處理方案數往往非常巨大題目通常要求對某個大數MOD如10^97取模。這里有一個極易出錯的細節必須在每一次加法運算后立即取模而不是最后才取模。因為中間結果可能已經溢出即使在Python這種大整數語言中取模操作本身也應在合理時機進行以保持一致性和效率。MOD 10**9 7 def dfs(pos, prev_color): ... total 0 for color in range(k): if color ! prev_color: total (total dfs(pos 1, color)) % MOD # 邊加邊模 dp[pos][prev_color] total return total同時要確保緩存中存儲的是取模后的值并且遞歸終點返回的1也要考慮取模雖然1 % MOD還是1。6.4 初始化與無效狀態處理對于使用數組緩存的情況初始化值如-1必須確保不會與任何有效結果混淆。如果有效結果可能為0或-1就需要選擇其他哨兵值或者使用一個單獨的visited布爾數組來記錄狀態是否已計算。另外要小心處理“無效狀態”。例如在“首尾不同色”問題中狀態(pos, prev_color, first_color)里的prev_color可能為-1起始時但first_color在起始時是未定義的。我們可以在遞歸函數開始時通過pos參數來區分是否需要檢查first_color或者用特殊的默認值來表示“未定義”。7. 實戰演練解決一個綜合性的著色問題讓我們用一個稍微復雜點的例子來整合所有知識點。問題描述用k種顏色涂n個排成一列的格子。約束如下相鄰格子顏色不同。第一個格子和最后一個格子顏色也不能相同。顏色0最多只能使用limit次。我們將使用記憶化搜索來解決它。7.1 狀態定義這個問題結合了“首尾不同色”和“顏色次數限制”。我們需要跟蹤當前處理到的位置pos(0到n)。前一個格子的顏色prev_color(-1到k-1)。第一個格子的顏色first_color(-1到k-1初始為-1表示未確定)。顏色0已經使用的次數used_zero(0到limit)。因此狀態是一個四元組(pos, prev_color, first_color, used_zero)。7.2 狀態轉移與邊界處理遞歸終點(pos n): 檢查是否滿足“首尾不同色”約束。即如果first_color ! -1且prev_color first_color則此方案無效返回0否則返回1。當前位置選擇顏色:遍歷所有顏色c(0 到 k-1)。約束1:c ! prev_color(除非prev_color -1即第一個格子)。約束3: 如果c 0則必須滿足used_zero 1 limit。狀態更新:new_used_zero used_zero (1 if c 0 else 0)new_first_color c if pos 0 else first_color(只有涂第一個格子時才確定first_color)遞歸調用dfs(pos1, c, new_first_color, new_used_zero)7.3 代碼實現與緩存由于狀態有四個維度且prev_color和first_color范圍是k1包含-1used_zero范圍是limit1使用四維數組可能代碼不夠清晰。這里我們使用functools.lru_cache配合元組作為鍵更為簡潔。from functools import lru_cache def solve_coloring(n, k, limit): MOD 10**9 7 lru_cache(maxsizeNone) def dfs(pos, prev_color, first_color, used_zero): # pos: 當前要涂的格子索引 (0-based) # prev_color: 上一個格子的顏色-1表示沒有上一個起始狀態 # first_color: 第一個格子的顏色-1表示尚未確定 # used_zero: 顏色0已經使用的次數 # 遞歸終點所有格子涂完 if pos n: # 檢查首尾顏色是否相同 if first_color ! -1 and prev_color first_color: return 0 # 違反約束2無效方案 return 1 # 找到一種合法方案 total 0 for color in range(k): # 約束1相鄰不能同色 (第一個格子跳過此檢查) if pos 0 and color prev_color: continue # 約束3顏色0使用次數限制 if color 0 and used_zero limit: continue # 計算新的狀態 new_used_zero used_zero (1 if color 0 else 0) # 如果是第一個格子記錄其顏色 new_first_color color if pos 0 else first_color total (total dfs(pos 1, color, new_first_color, new_used_zero)) % MOD return total % MOD # 初始狀態從第0個格子開始前一個顏色無(-1)第一個顏色未定(-1)顏色0已使用0次 return dfs(0, -1, -1, 0) # 測試 n, k, limit 4, 3, 1 print(solve_coloring(n, k, limit)) # 輸出符合約束的方案數7.4 分析與優化點這個解法直接、清晰但狀態空間是O(n * k * k * limit)。如果k和limit不大比如都10n在100左右是完全可行的。如果k很大我們可以注意到對于“顏色0”的特殊限制我們只額外跟蹤了它的使用次數而其他顏色是“無限制”且對稱的。這提示我們狀態中可以只區分“顏色0”和“非顏色0的其他顏色”而不是具體是哪種顏色從而將k的影響從狀態中部分剝離優化狀態數量。這種基于對稱性的優化是解決大規模計數問題的進階技巧。通過這個綜合例子你應該能感受到記憶化搜索就像一套“萬能模具”。面對新的約束我們主要的工作是設計出包含足夠信息的狀態表示然后遞歸關系往往可以比較直接地根據題意寫出來。剩下的就交給緩存去優化效率。這種“定義狀態描述轉移緩存結果”的三段式思維是解決一大類組合計數問題的核心方法論。