題目

給定數字 $$N$$，組成像這樣的圖共有 $$2N$$ 個節點

1
2
3

O ── O ── ... ── O
|    |    ...    |
O ── O ── ... ── O

刪除一些邊使得圖依然連通，共有幾種刪法?

解法

原本想說如果左邊連通再加兩個節點的話 $$dp_{i}=3dp_{i-1}$$
但有可能左邊原本沒連通後來加三個邊所以連通了。

設 $$dp_{i,0/1}$$ 為圖分成兩部分或連通的刪除方法數。
如果分兩部分最右邊兩節點不能在同一連通塊，否則以後不能把圖連起來了。

1
2

dp[i][0] = 4 * dp[i][0] + dp[i][1];
dp[i][1] = 2 * dp[i][0] + dp[i][1];

一個狀態不能解決問題，那就兩個。就算只有 0/1 也能造成很大的效果。