スコルの知恵袋

主にプログラミング関係の気になったこと等をまとめたブログ

DPの配列使いまわしテクニックに関するメモ

この記事は swap を使った配列使いまわしテクニックのメモ。

インデックスの偶奇を使った配列使いまわしテクニックは蟻本の悪習だという話を聞いた。確かに、この方法ではコードの見た目は悪いし、「初期化 or 出力するのは偶奇のどっちの配列だろう?」とかを考える手間が生じる。 これを回避するために、偶奇で更新する配列を判断する代わりに、dp1 を古い配列、dp2 を新しい配列と決めて、配列を swap しながら DP する。

DP配列の swap に関する注意

配列の swap では注意すべきことがあって、下のようにするとメモリ上の実体が swap されるので  O(N) かかってしまう。

int dp1[N], dp2[N];
swap(dp1, dp2);

これを避けるには次のようにする。

int dp[2][N];
auto dp1 = dp[0];
auto dp2 = dp[1];
swap(dp1, dp2);

こっちはポインタが swap されるだけなので  O(1) で済む。また、多次元でも同じ。

int dp[2][N][M][K];
auto dp1 = dp[0];
auto dp2 = dp[1];
swap(dp1, dp2);

vector を使っても  O(1) で swap できるけど、気分的にDPに vector はあんまり使いたくない。多次元ならなおさら嫌。

ナップサックDP

ナップサックDPをこの方法で実装するとこうなる。

ll dp[2][100010];
 
void solve() {
    ll N, W;
    cin >> N >> W;
    Vl ws(N), vs(N);
    for (ll i = 0; i < N; i++) {
        cin >> ws[i] >> vs[i];
    }
 
    auto dp1 = dp[0];
    auto dp2 = dp[1];
    for (ll i = 0; i < N; i++) {
        swap(dp1, dp2);
        memset(dp2, 0, sizeof(ll) * W);
        for (ll j = 0; j <= W; j++) {
            dp2[j] = dp1[j];
            if (j - ws[i] >= 0)
                chmax(dp2[j], dp1[j - ws[i]] + vs[i]);
        }
    }
 
    prints()(dp2[W]);
}