DPのメモリ節約方法 - 早稲田大学チームvivid_turtle 知見共有@ ウィキ

動的計画法の問題で、時間計算量は問題ないのに、空間計算量が厳しい、というタイプはある。その時のいくつかの対策法をここに記す。

漸化式で定数個前までしかいらない場合

有名な例としてはフィボナッチ数列(2つ前しか見ない)やナップサック問題(1つ前しか見ない)だろう。

この時、「動的計画法の配列でよくある何個目まで見た」という添え字を消して、うまく配列を再利用すればメモリの次元を一つ落とせる。

特に、1つ前しか見ないタイプは次のテンプレを使うといい。

int dp[2][1000];
auto now = dp[0], nxt = dp[1];
 
for (int i = 1; i < n; i++){
	for(int j = 0; j < 1000; j++){
        //操作例を示す
        if(j - K > 0){
            nxt = min(now[j] + j, now[j - K] + j * j);
        }
    }
    //１つのiに関しての操作を終えたら、nowとnxtを交換することによって、配列の再利用をスマートに書ける。
    swap(now, nxt);
}
 

他の添え字の持つ情報に包含されてるもの

上記のような再利用以外での抜本的な改善法は、落としたい添え字の持つ情報はほかの添え字と同じ、もしくはそれから一定の値に定められるのならば、その添え字は消してよい。
この改善を行うことで、物によっては時間計算量もオーダーがが一つ落ちる場合がある。

具体的な例としては、

dp[i][j][k]で、よく考えたらj == kしかないときは、dp[i][j]として問題ない。

bitdp配列、dp[i][bit]でiは何個目まで見たか、bitがどれを使ったかなどで、iがbitのたってる個数と一致する場合、dp[bit]にして、毎ループごとに自分自身を更新するようにしても問題はない。

EDPC O Matching

https://atcoder.jp/contests/dp/tasks/dp_o

この問題では、少し考えるとbitdp配列
dp[i][bit] := i人目の男までマッチングを終えて、bitのような状態で女が残ってる。
と定めれば時間計算量的に更新が間に合う。しかし、メモリは厳しい。ここで、さきほどの具体例2つ目を考えると、iの添え字は不要。