1. 項(xiàng)目概述從一道國(guó)賽真題看DFS的實(shí)戰(zhàn)應(yīng)用最近在復(fù)盤(pán)藍(lán)橋杯國(guó)賽的歷年真題發(fā)現(xiàn)“矩陣計(jì)數(shù)”這類(lèi)題目出現(xiàn)的頻率相當(dāng)高而且常常作為區(qū)分選手能力的關(guān)鍵題。它不像一些純模擬題那樣直接也不像動(dòng)態(tài)規(guī)劃那樣有固定的套路模板更多是考察對(duì)搜索算法的深入理解和靈活應(yīng)用能力。題目通常會(huì)給一個(gè)矩陣的規(guī)模比如 n x m以及一些限制條件比如矩陣中只能填0或1并且要求不存在某些特定的子矩陣模式例如2x2的子矩陣全為1然后問(wèn)滿(mǎn)足條件的矩陣有多少種。這本質(zhì)上是一個(gè)狀態(tài)空間搜索問(wèn)題而深度優(yōu)先搜索DFS正是解決這類(lèi)問(wèn)題的利器。我剛接觸這類(lèi)題時(shí)第一反應(yīng)是暴力枚舉——每個(gè)格子要么0要么1那直接2^(n*m)種可能全試一遍不就行了但稍微算一下就知道不可行一個(gè)5x5的矩陣就有2^25約3300萬(wàn)種狀態(tài)更別說(shuō)國(guó)賽常見(jiàn)的更大規(guī)模了。這就需要DFS結(jié)合剪枝技巧在搜索樹(shù)構(gòu)建的早期就果斷砍掉大量不可能到達(dá)最終解的分支。這不僅僅是寫(xiě)一個(gè)遞歸函數(shù)那么簡(jiǎn)單它涉及到如何高效地表示狀態(tài)、如何設(shè)計(jì)搜索順序以減少冗余、以及如何挖掘題目條件設(shè)計(jì)出強(qiáng)有力的剪枝策略。接下來(lái)我就結(jié)合自己的解題經(jīng)驗(yàn)拆解一下這類(lèi)問(wèn)題的通用思路和幾個(gè)關(guān)鍵的實(shí)現(xiàn)技巧。2. 問(wèn)題核心與DFS建模思路拆解2.1 問(wèn)題本質(zhì)與狀態(tài)定義“矩陣計(jì)數(shù)”問(wèn)題的核心是統(tǒng)計(jì)滿(mǎn)足特定約束的所有可能矩陣的數(shù)量。約束條件千變?nèi)f化但最常見(jiàn)的兩類(lèi)是局部形狀約束例如禁止出現(xiàn)任何2x2的子矩陣全部為1或全部為0。這是藍(lán)橋杯非常愛(ài)考的一類(lèi)因?yàn)樗芎芎玫匾觥盎诋?dāng)前位置的可行性判斷”這一剪枝思想。行列統(tǒng)計(jì)約束例如每一行1的個(gè)數(shù)、每一列1的個(gè)數(shù)需要滿(mǎn)足某個(gè)條件。無(wú)論約束如何我們都可以將矩陣的填充過(guò)程看作在一個(gè) n x m 的網(wǎng)格上進(jìn)行DFS。每個(gè)格子是一個(gè)“搜索層”我們需要決定在這個(gè)格子填0還是填1。狀態(tài)如何表示最直接的想法是用一個(gè)二維數(shù)組matrix[n][m]來(lái)記錄當(dāng)前填充的狀態(tài)-1表示未填充0或1表示已填充。DFS函數(shù)簽名可能像這樣dfs(row, col)表示當(dāng)前要填充第row行、第col列的格子。搜索順序的設(shè)計(jì)這很重要。按行優(yōu)先從左到右從上到下的順序進(jìn)行填充是最自然、也是最有利于剪枝的。因?yàn)楫?dāng)我們填充到(row, col)時(shí)它左上方的所有格子都已經(jīng)確定了我們可以利用這些已知信息來(lái)判斷當(dāng)前選擇是否會(huì)導(dǎo)致后續(xù)無(wú)解。2.2 DFS遞歸框架的搭建一個(gè)清晰的遞歸框架是基礎(chǔ)。假設(shè)矩陣大小為n行m列我們從(0, 0)開(kāi)始搜索。def dfs(pos): # pos 是當(dāng)前要處理的格子編號(hào) pos row * m col if pos n * m: # 所有格子都處理完了 if check_all(): # 檢查整個(gè)矩陣是否滿(mǎn)足最終約束 global count count 1 return row pos // m col pos % m # 嘗試在當(dāng)前格子填 0 matrix[row][col] 0 if is_partial_valid(row, col): # 關(guān)鍵剪枝部分合法才繼續(xù) dfs(pos 1) # 回溯 matrix[row][col] -1 # 嘗試在當(dāng)前格子填 1 matrix[row][col] 1 if is_partial_valid(row, col): dfs(pos 1) # 回溯 matrix[row][col] -1這個(gè)框架很簡(jiǎn)單但有兩個(gè)關(guān)鍵函數(shù)check_all(): 當(dāng)矩陣填滿(mǎn)后進(jìn)行全局的、徹底的約束檢查。它只在到達(dá)葉子節(jié)點(diǎn)時(shí)調(diào)用一次。is_partial_valid(row, col):這是剪枝的靈魂。它在每次做出選擇填0或1后立即調(diào)用判斷在當(dāng)前這個(gè)部分填充的狀態(tài)下是否已經(jīng)必然違反了題目約束。如果已經(jīng)違反就沒(méi)必要繼續(xù)向下搜索了直接回溯。對(duì)于“禁止2x2全1”這種約束is_partial_valid的實(shí)現(xiàn)非常高效我們只需要檢查以當(dāng)前新填充的格子(row, col)作為右下角的2x2子矩陣如果存在的話(huà)是否非法。因?yàn)楫?dāng)我們?cè)谔畛?row, col)時(shí)它左上方的(row-1, col-1),(row-1, col),(row, col-1)這三個(gè)格子如果坐標(biāo)合法的狀態(tài)是已知的。如果這三個(gè)格子都是1并且當(dāng)前我們也填1那么這個(gè)2x2子矩陣就全為1了當(dāng)前狀態(tài)就是非法的必須剪枝。def is_partial_valid(row, col): # 檢查以 (row, col) 為右下角的潛在2x2子矩陣 # 只需要檢查當(dāng)前格子填1的情況因?yàn)樘?不可能構(gòu)成全1矩陣 if matrix[row][col] 1: # 檢查左上、上、左三個(gè)格子 if row 1 and col 1: if matrix[row-1][col-1] 1 and matrix[row-1][col] 1 and matrix[row][col-1] 1: return False # 發(fā)現(xiàn)非法2x2全1子矩陣 return True這個(gè)剪枝的威力巨大它能在搜索的早期就排除掉大量無(wú)效分支。實(shí)測(cè)下來(lái)沒(méi)有這個(gè)剪枝5x5的矩陣都跑得吃力加上之后10x10甚至更大規(guī)模的矩陣都有可能在一定時(shí)間內(nèi)求解。3. 核心優(yōu)化技巧與實(shí)戰(zhàn)細(xì)節(jié)3.1 狀態(tài)壓縮與記憶化搜索當(dāng)矩陣規(guī)模增大或者約束條件更復(fù)雜時(shí)單純的DFS剪枝可能依然會(huì)超時(shí)。這時(shí)就需要更高級(jí)的優(yōu)化。狀態(tài)壓縮是一個(gè)經(jīng)典思路。對(duì)于按行優(yōu)先搜索當(dāng)我們處理到第i行第j列時(shí)哪些信息是對(duì)后續(xù)搜索有決定性影響的對(duì)于“禁止2x2全1”問(wèn)題當(dāng)前行i的填充狀態(tài)以及上一行i-1的填充狀態(tài)共同決定了下一行哪些位置不能填1否則會(huì)與上一行形成非法的2x2。我們可以用二進(jìn)制位來(lái)壓縮一行的狀態(tài)。例如一個(gè)寬度為m的列每一列填1或0可以用一個(gè)m位的二進(jìn)制數(shù)來(lái)表示第k位為1表示該列填1。這樣我們的DFS狀態(tài)就可以定義為dfs(i, prev_state, curr_state, col)表示i: 當(dāng)前正在填充的行號(hào)。prev_state: 上一行i-1行的壓縮狀態(tài)。curr_state: 當(dāng)前行i行已經(jīng)填充到第col列時(shí)的狀態(tài)。col: 當(dāng)前正在填充的列號(hào)。那么is_partial_valid檢查就變成了位運(yùn)算當(dāng)我們要在(i, col)位置填1時(shí)需要檢查prev_state的第col位、以及curr_state的第col-1位如果存在是否都是1。這比操作二維數(shù)組快得多。更進(jìn)一步我們可以引入記憶化搜索Memoization。狀態(tài)(i, prev_state, col)可能被重復(fù)計(jì)算多次。如果我們用DP的思想把dfs(i, prev_state, col)定義為“從第i行、第col列開(kāi)始在上一行狀態(tài)為prev_state的約束下能填出多少種合法的剩余矩陣”那么就可以把結(jié)果緩存起來(lái)。當(dāng)再次遇到相同的(i, prev_state, col)時(shí)直接返回緩存結(jié)果避免重復(fù)搜索子樹(shù)。from functools import lru_cache lru_cache(maxsizeNone) def dfs(row, prev_state, col): if col m: # 當(dāng)前行填完進(jìn)入下一行 return dfs(row 1, curr_state, 0) if row n: # 所有行都填完找到一種合法方案 return 1 total 0 # 嘗試填0 total dfs(row, prev_state, col 1) # 嘗試填1需要檢查是否與上一行形成非法2x2 # 檢查條件不能同時(shí)滿(mǎn)足 (prev_state在col位為1) 且 (col0時(shí)curr_state在col-1位為1) 且 (prev_state在col-1位為1) # 這里curr_state是當(dāng)前行已填充的狀態(tài)我們需要在遞歸調(diào)用前判斷 # 更常見(jiàn)的寫(xiě)法是在決定填1時(shí)構(gòu)造新的new_curr_state然后判斷(new_curr_state, prev_state)是否合法 # 判斷函數(shù) is_valid_transition(prev_state, new_curr_state) new_curr_state curr_state | (1 col) if is_valid_transition(prev_state, new_curr_state): total dfs(row, new_curr_state, col 1) return total這種“DFS狀態(tài)壓縮記憶化”的組合拳能將指數(shù)級(jí)復(fù)雜度的搜索問(wèn)題轉(zhuǎn)化為狀態(tài)數(shù)可控的動(dòng)態(tài)規(guī)劃問(wèn)題。狀態(tài)數(shù)大約是n * (2^m) * m當(dāng)m較小時(shí)比如 m10這個(gè)方法是完全可行的。這也是國(guó)賽題常見(jiàn)的套路考察選手能否將搜索問(wèn)題轉(zhuǎn)化為狀壓DP。3.2 搜索順序與對(duì)稱(chēng)性剪枝除了基于約束的剪枝利用問(wèn)題的對(duì)稱(chēng)性也能大幅減少搜索量。在很多矩陣計(jì)數(shù)問(wèn)題中矩陣是方陣nm或者問(wèn)題本身具有旋轉(zhuǎn)、翻轉(zhuǎn)對(duì)稱(chēng)性。這些對(duì)稱(chēng)的方案在本質(zhì)上被視為同一種但我們的DFS會(huì)每一種都枚舉出來(lái)導(dǎo)致重復(fù)計(jì)數(shù)。例如一個(gè)關(guān)于中心點(diǎn)旋轉(zhuǎn)90度后相同的矩陣我們只應(yīng)計(jì)數(shù)一次。一種處理方法是在搜索過(guò)程中加入規(guī)范化Canonical表示?；舅悸肥菍?duì)于每個(gè)填充到一半或完整的矩陣我們計(jì)算出它所有對(duì)稱(chēng)變換下的“最小”或“標(biāo)準(zhǔn)”表示比如轉(zhuǎn)化為字符串后取字典序最小的。在搜索過(guò)程中如果發(fā)現(xiàn)當(dāng)前部分填充的狀態(tài)其規(guī)范表示不等于它自身說(shuō)明它可以通過(guò)對(duì)稱(chēng)性由“更小”的狀態(tài)得到那么當(dāng)前分支就可以剪掉因?yàn)樽罱K它會(huì)被那個(gè)“更小”的狀態(tài)搜索到并計(jì)數(shù)。實(shí)現(xiàn)對(duì)稱(chēng)性剪枝通常比較復(fù)雜需要仔細(xì)處理部分填充狀態(tài)下的判斷。在競(jìng)賽時(shí)間有限的情況下一個(gè)更實(shí)用的策略是先不考慮對(duì)稱(chēng)性用DFS算出總數(shù)量包含重復(fù)如果題目要求的是“本質(zhì)不同”的數(shù)量再根據(jù)對(duì)稱(chēng)群的規(guī)模如正方形旋轉(zhuǎn)有4種加上翻轉(zhuǎn)可能8種去除以相應(yīng)的數(shù)。但要注意這種方法的前提是所有方案都恰好被每個(gè)對(duì)稱(chēng)操作映射到不同的方案即沒(méi)有“自對(duì)稱(chēng)”的方案。如果存在自對(duì)稱(chēng)的矩陣比如全0矩陣它不會(huì)被重復(fù)計(jì)數(shù)那么多次直接除法會(huì)導(dǎo)致錯(cuò)誤。這時(shí)就需要用到Burnside引理或Polya計(jì)數(shù)定理來(lái)準(zhǔn)確計(jì)算這就涉及到更深的組合數(shù)學(xué)知識(shí)了在國(guó)賽中出現(xiàn)屬于壓軸難度。3.3 邊界處理與代碼魯棒性在實(shí)現(xiàn)DFS時(shí)邊界條件的處理是bug的高發(fā)區(qū)。數(shù)組越界在is_partial_valid函數(shù)中檢查(row-1, col-1)等格子時(shí)務(wù)必先判斷row1和col1。我早期經(jīng)常在這里寫(xiě)出if matrix[row-1][col-1]...而忘記檢查下標(biāo)導(dǎo)致程序在搜索第一行或第一列時(shí)崩潰。狀態(tài)回溯這是DFS的基石必須成對(duì)出現(xiàn)。我習(xí)慣采用“做出選擇-遞歸-撤銷(xiāo)選擇”的模式如上文代碼所示。在Python中對(duì)于整數(shù)等不可變對(duì)象在參數(shù)傳遞時(shí)是值傳遞天然具有回溯效果。但對(duì)于列表、字典等可變對(duì)象或者在C中使用全局?jǐn)?shù)組就必須手動(dòng)回溯。一個(gè)常見(jiàn)的錯(cuò)誤是忘記在遞歸返回后撤銷(xiāo)選擇導(dǎo)致?tīng)顟B(tài)污染。遞歸深度Python的默認(rèn)遞歸深度限制通常1000對(duì)于 n*m 較大的矩陣可能不夠。例如一個(gè)30x30的網(wǎng)格遞歸深度就達(dá)到900。你需要使用sys.setrecursionlimit(1000000)來(lái)提高限制。但更根本的方法是評(píng)估問(wèn)題規(guī)模如果實(shí)在太大可能就需要用迭代加深搜索IDS或者更高級(jí)的算法了。4. 從DFS到動(dòng)態(tài)規(guī)劃的思維跨越對(duì)于“矩陣計(jì)數(shù)”這類(lèi)問(wèn)題DFS是直觀(guān)的起點(diǎn)但高效的解法往往最終落腳在動(dòng)態(tài)規(guī)劃DP特別是狀壓DP。我們可以把DFS的記憶化搜索過(guò)程明確地寫(xiě)成DP遞推式。定義dp[i][state]表示已經(jīng)填充完前i行并且第i行的填充狀態(tài)為state二進(jìn)制壓縮時(shí)合法的方案數(shù)。 那么狀態(tài)轉(zhuǎn)移方程為dp[i][curr_state] sum(dp[i-1][prev_state] for prev_state in all_states if is_valid_transition(prev_state, curr_state))其中is_valid_transition(prev_state, curr_state)函數(shù)判斷從上一行狀態(tài)prev_state到當(dāng)前行狀態(tài)curr_state是否合法。對(duì)于“禁止2x2全1”的約束這個(gè)判斷就是對(duì)于任意相鄰兩列j和j1不能出現(xiàn)prev_state的第j位、第j1位以及curr_state的第j位、第j1位同時(shí)為1。這同樣可以用位運(yùn)算快速判斷。def is_valid_transition(prev, curr): # 假設(shè)矩陣寬度為m # 檢查是否存在連續(xù)的列j使得 prev和curr在這些列上都是1 # 即 (prev curr) 的任意連續(xù)兩位不能都為1 combined prev curr # 檢查combined中是否有連續(xù)的1 # 方法將combined與自身左移一位進(jìn)行與操作結(jié)果不為0則說(shuō)明有連續(xù)1 return (combined (combined 1)) 0初始化dp[0][0] 1第0行可以認(rèn)為是全0的空行只有1種狀態(tài)。最終答案就是sum(dp[n][state] for state in all_states)。這種DP方法的時(shí)間復(fù)雜度是O(n * (2^m) * (2^m))因?yàn)閷?duì)于每個(gè)dp[i][curr]我們需要遍歷所有可能的prev。當(dāng)m較大時(shí)比如15狀態(tài)數(shù)2^1532768兩兩判斷的復(fù)雜度是1e9級(jí)別依然會(huì)超時(shí)。這時(shí)需要進(jìn)一步優(yōu)化例如預(yù)處理出每個(gè)狀態(tài)所有合法的“下一行狀態(tài)”列表避免內(nèi)層循環(huán)遍歷所有狀態(tài)。5. 實(shí)戰(zhàn)案例分析與調(diào)試心得5.1 案例藍(lán)橋杯典型題“方格計(jì)數(shù)”變種假設(shè)題目是在 n x m 的矩陣中填0/1要求不存在任何2x2的子矩陣全為1。求方案數(shù)。n, m 10。思路選擇n和m都不大但最大10x10狀態(tài)空間2^100巨大必須剪枝。由于約束是局部的2x2按行優(yōu)先DFS配合“右下角檢查”剪枝是可行的。但為了更優(yōu)可以采用狀壓DP。DP實(shí)現(xiàn)關(guān)鍵點(diǎn)狀態(tài)表示dp[row][state]state是當(dāng)前行的二進(jìn)制壓縮。合法性檢查行內(nèi)合法性state本身不能有連續(xù)的1因?yàn)槿绻恍袃?nèi)有兩個(gè)連續(xù)的1并且上一行對(duì)應(yīng)位置也是1就會(huì)形成2x2。所以合法的state需要滿(mǎn)足(state (state 1)) 0。行間合法性對(duì)于上一行狀態(tài)prev和當(dāng)前行狀態(tài)curr需要滿(mǎn)足(prev curr) ((prev curr) 1) 0。即兩行按位與的結(jié)果不能有連續(xù)的1。初始化dp[0][0] 1。注意第0行是虛擬行狀態(tài)0代表全0。結(jié)果sum(dp[n][state])其中state是任意合法狀態(tài)。def solve(n, m): all_states [] # 預(yù)處理所有行內(nèi)合法的狀態(tài) for s in range(1 m): if s (s 1) 0: # 沒(méi)有連續(xù)的1 all_states.append(s) # 預(yù)處理狀態(tài)轉(zhuǎn)移關(guān)系from_state - [to_state_list] transition {s: [] for s in all_states} for s1 in all_states: for s2 in all_states: if (s1 s2) ((s1 s2) 1) 0: transition[s1].append(s2) dp [ [0] * (1 m) for _ in range(n1) ] dp[0][0] 1 # 虛擬第0行狀態(tài)為0 for i in range(1, n1): for prev in all_states: if dp[i-1][prev] 0: continue for curr in transition[prev]: dp[i][curr] dp[i-1][prev] ans sum(dp[n][s] for s in all_states) return ans5.2 調(diào)試與驗(yàn)證技巧從小規(guī)模驗(yàn)證永遠(yuǎn)從最小的數(shù)據(jù)開(kāi)始測(cè)試。比如 n1, m1答案應(yīng)該是2[0], [1]。n2, m2手動(dòng)枚舉所有16種矩陣排除掉包含2x2全1的其實(shí)只有一種全1矩陣答案應(yīng)該是15。用你的程序跑一下看結(jié)果是否匹配。輸出中間狀態(tài)在DFS中可以打印出搜索到某個(gè)深度時(shí)的矩陣狀態(tài)或者DP中每行的方案數(shù)看看是否符合預(yù)期。對(duì)于DP計(jì)算完dp[1]即第一行后dp[1][state]應(yīng)該等于行內(nèi)合法的、狀態(tài)為state的方案數(shù)這很容易驗(yàn)證。對(duì)拍寫(xiě)一個(gè)暴力枚舉程序僅適用于非常小的n和m比如n,m4用它來(lái)生成小數(shù)據(jù)下的正確答案。然后用你的優(yōu)化算法去跑同樣的數(shù)據(jù)對(duì)比結(jié)果是否一致。這是檢驗(yàn)算法正確性最可靠的方法之一。時(shí)間復(fù)雜度估算在提交前估算最壞情況下的操作次數(shù)。例如上述DP解法預(yù)處理transition是 O( (2^m)^2 )主循環(huán)是 O(n * (2^m) * avg_transition)。當(dāng) m10時(shí)2^m1024平方約1e6主循環(huán)假設(shè)平均轉(zhuǎn)移數(shù)100n10則約1e6次操作完全在1秒內(nèi)。做到心中有數(shù)避免盲目提交導(dǎo)致超時(shí)。5.3 常見(jiàn)“坑點(diǎn)”實(shí)錄整數(shù)溢出方案數(shù)可能非常大遠(yuǎn)超int范圍。在C中要使用long long在Python中雖然整數(shù)不限但也要注意。藍(lán)橋杯的題目有時(shí)會(huì)要求取模一定要看清楚題目要求在每次加法或乘法后及時(shí)取模。初始化錯(cuò)誤DP中dp[0][0]1是常見(jiàn)的初始化。但有些題目中第一行可能有特殊限制比如第一行不能全0那么初始化就需要改變。務(wù)必結(jié)合題意理解“第0行”這個(gè)虛擬狀態(tài)的含義。位運(yùn)算優(yōu)先級(jí)和的優(yōu)先級(jí)問(wèn)題。if s (s 1) 0:在Python中是錯(cuò)誤的因?yàn)閮?yōu)先級(jí)高于。必須寫(xiě)成if (s (s 1)) 0:。這是我早期常犯的錯(cuò)誤調(diào)試起來(lái)很痛苦因?yàn)檫壿嬌峡床怀鰡?wèn)題。狀態(tài)表示歧義用二進(jìn)制位表示一行狀態(tài)時(shí)第0位是最低位代表最右邊的列還是最高位代表最左邊的列這需要統(tǒng)一。我習(xí)慣讓state的第j位對(duì)應(yīng)第j列從0開(kāi)始。在檢查連續(xù)列時(shí)左移操作 1就對(duì)應(yīng)檢查相鄰的下一列列號(hào)1。只要在整個(gè)程序中保持一致即可。6. 性能瓶頸分析與進(jìn)階策略當(dāng) n 和 m 繼續(xù)增大比如到15以上無(wú)論是DFS剪枝還是標(biāo)準(zhǔn)的狀壓DP都可能面臨性能壓力。這時(shí)需要思考更精妙的優(yōu)化。1. 滾動(dòng)數(shù)組優(yōu)化DP數(shù)組dp[i][state]只依賴(lài)于dp[i-1][state]所以可以只用兩個(gè)一維數(shù)組dp_curr和dp_prev交替使用將空間復(fù)雜度從 O(n * 2^m) 降到 O(2^m)。2. 矩陣快速冪優(yōu)化如果題目中的約束是“行間無(wú)關(guān)”的即下一行的合法狀態(tài)只依賴(lài)于上一行的狀態(tài)并且這個(gè)轉(zhuǎn)移關(guān)系對(duì)于每一行都是相同的就像我們上面討論的“禁止2x2全1”那么整個(gè)填充過(guò)程可以看作一個(gè)狀態(tài)轉(zhuǎn)移矩陣的連乘。定義矩陣M其大小是S x SS是合法狀態(tài)數(shù)M[prev][curr] 1當(dāng)且僅當(dāng)從狀態(tài)prev轉(zhuǎn)移到curr是合法的。那么從第0行虛擬行狀態(tài)0到第n行的方案數(shù)就是向量[1, 0, 0, ...]只有狀態(tài)0為1乘以矩陣M^n后所有元素的和。計(jì)算M^n可以使用矩陣快速冪時(shí)間復(fù)雜度為 O(S^3 * log n)。當(dāng)合法狀態(tài)數(shù) S 不大比如幾百而 n 非常大比如10^9時(shí)這種方法極其高效。這通常出現(xiàn)在“鋪瓷磚”一類(lèi)的問(wèn)題中。3. 輪廓線(xiàn)DP插頭DP對(duì)于更復(fù)雜的連通性約束比如要求所有1的格子構(gòu)成一條路徑或者要求1的連通塊數(shù)量等狀壓DP每一行記錄一個(gè)狀態(tài)就不夠了需要記錄當(dāng)前處理格子所在“輪廓線(xiàn)”上的更細(xì)致?tīng)顟B(tài)。這是競(jìng)賽中的高級(jí)話(huà)題難度很大但也是解決復(fù)雜矩陣計(jì)數(shù)問(wèn)題的終極武器之一。它本質(zhì)上是將狀態(tài)壓縮與DP結(jié)合到了極致按格遞推狀態(tài)表示當(dāng)前已經(jīng)處理過(guò)的格子和未處理格子之間的“分界線(xiàn)”上的情況。面對(duì)國(guó)賽級(jí)別的矩陣計(jì)數(shù)題我的策略通常是先嘗試最直觀(guān)的DFS剪枝寫(xiě)一個(gè)暴力版本用于驗(yàn)證小數(shù)據(jù)思路。然后分析約束的局部性嘗試轉(zhuǎn)化為狀壓DP。如果數(shù)據(jù)范圍暗示 n 大 m 小就采用標(biāo)準(zhǔn)狀壓DP如果 m 也偏大就要考慮是否有特殊的性質(zhì)可以簡(jiǎn)化狀態(tài)比如利用對(duì)稱(chēng)性減少狀態(tài)數(shù)或者是否需要用到輪廓線(xiàn)DP。平時(shí)多積累不同約束對(duì)應(yīng)的狀態(tài)表示和轉(zhuǎn)移方法比賽時(shí)才能快速識(shí)別并套用。