插頭DP學習筆記 用途 有些 狀壓 \(DP\) 問題要求我們記錄狀態的連通性信息,這類問題一般被形象的稱為插頭 \(DP\) 或連通性狀態壓縮 \(DP\) 例如格點圖的哈密頓路徑計數,求棋盤的黑白染色方案滿足相同顏色之間形成一個連通塊的方案數,以及特定圖的生成樹計數等等。 這些問題通常需要我們對狀態的連通性進行編碼,討論狀態轉移過程中連通性的變化。