Contents

揭開DP狀態壓縮的神秘面紗

DP狀態壓縮可以優化空間複雜度,通常用於狀態只依靠鄰近狀態時,可以把二維的狀態壓縮成一維來表示。是不是聽到這裡覺得,狀壓是一個很猛的,只有聰明人會用的東西?不,這篇文章就是來為你解開狀態壓縮神秘的面紗,希望透過這篇文章,可以讓每個讀者都輕鬆寫出狀態壓縮。

案例介紹

我非常不建議一開始就學狀態壓縮的寫法,應該先寫好高維的表示方式再進行降維。多說無益,這裏就給個案例 - Leetcode 494 - TargetSum。這題的解法不是此篇文章探討的重點,所以我只會focus在優化的部分。這題用dfs會超時,可以換成背包問題:求子集總和為target的方法數。背包問題有兩個狀態:一是目前可以挑的物品,另外一個則是背包剩下的容量,狀態轉移方程如下:

1
2
3
4
//if pick the number
dp[i][sum] = dp[i - 1][sum - current_num] + dp[i - 1][sum]
//if not pick
dp[i][sum] = dp[i - 1][sum]

有了狀態轉移方程就很容易實現了。

1
2
3
4
5
6
7
8
for(int i = 1; i <= n; i++) {
    for(int j = 0; j <= target; j++) {
        if(j - nums[i - 1] >= 0) 
            dp[i][j] = dp[i - 1][j - nums[i - 1]] + dp[i - 1][j];
        else
            dp[i][j] = dp[i - 1][j];
    }
}

每一個i的狀態都只需要依賴i - 1的值,所以或許我們根本不需要紀錄那麼多i的狀態,因此這個解法還可以進行優化。下一部分就是本文重點:狀態壓縮。

狀態壓縮

在for迴圈中,我們每一次只要紀錄一個i的狀態,但如果我把dp[i][sum] = dp[i - 1][sum - cur_num] + dp[i][sum]直接改成dp[sum] = dp[sum - current_num] + dp[sum],會出現很大的問題喔 😨 問題的原因是什麼呢?讓我們先看看下面這張圖:
/1-3-21/array.png
我們更新狀態的方向是由左到右(j的方向),由上到下(i的方向)。舉我們上面黑2的狀態,更新它的方法數需要紅1紅2的方法數。當我進行狀態壓縮時(變成下面一維的狀態),我會發現:咦?在我更新黑2前,紅1就已經被更新成橘1了誒!
問題就在於更新順序。那不如我們換個更新順序看看?我們把更新順序(j的方向)換成逆向,要更新黑2的時候紅1還沒被更新到,所以我們所需的方法數就沒有被改動到囉!因此優化後的代碼就能寫出來囉:

1
2
3
4
5
6
for(int i = 0; i < n; i++) {
    for(int j = target; j >= 0; j--) {
        if(j - nums[i] >= 0) 
            dp[j] += dp[j - nums[i]];
    }
}

總結

常常會看到有些人dp代碼寫得特別簡單,真不知道他哪來的思路,他絕對是個天才,其實也只不過是經歷上面這個過程的優化… 想寫出這個優化,把狀態和轉移的過程畫出來就明確很多了!回去看看leetcode上面股票買賣系列的文章,可能我們會覺得討論區中的代碼怎麼都這麼簡單,幾個變數就把狀態轉移方程表示完成?其實也只是壓縮完用變數把前一個所需的狀態存起來而已!如果覺得我圖畫得不夠明確或者想提供其他優化思路,歡迎留言討論喔 👍