AOJ DP libraryメモ

勉強

http://judge.u-aizu.ac.jp/onlinejudge/topic.jsp?cid=DPL
とりあえず、典型DPと呼ばれるであろう問題を一通り解く。
考えが違っていた部分をメモ。

Combinatorial A. Coin Changing Problem

dp[i][j]と置くとき、i-1からi方向しか考えない場合が多かったけど、「無限個使える」場合は、forループが1つ増えてしまう。
j-1までも計算済みであることを使えばループを減らせる。

Combinatorial B. 0-1 Knapsack Problem

。

Combinatorial C. Knapsack Problem

Coin + 0-1 Knapsack。

Combinatorial D. Longest Increasing Subsequence

LISはdpテーブルの持ち方をABCで見ていた。
dpテーブルの探索が必要な場合、dpテーブル自体のデータ構造も変更する必要がでてくる。

Combinatorial E. Edit Distance (Levenshtein Distance)

。

Permutation/Path A. Traveling Salesman Problem

bitDPで、dp[S][i][j]:=すでに訪れた頂点集合Sで、最初にスタートした頂点iと今いる頂点j、というテーブルでまとめて計算したけど、スタートする頂点ごとにV回計算しても同じなので、メモリがきついときはdp[S][j]で通せる。

Permutation/Path B. Chinese Postman Problem

有向グラフだと思ってずっと考えてたけど、無向グラフだった。。
すべての辺は1度以上通る、偶数次数と奇数次数の頂点数、奇数次数の処理、の考察が必要。
重み付き完全グラフの最小マッチングはbitDPで、TravelingSalesmanと同じ集合処理。

Pattern A. Largest Square

dp[i][j]を考える時、dp[i-1][j-1]と縦方向・横方向の空いているマス目が必要だと思って書いたけど、縦方向、横方向はdp[i-1][j]とdp[i][j-1]にも情報として含まれているので、それを使うことができる。

Pattern B. Largest Rectangle

ヒストグラム最大長方形問題。長方形の候補がたくさんでてくるのでうまく保持する必要がある。
j'から伸び続けている長方形でj時点でその長方形がさらに伸ばせるか？、j-1で終わりか？をうまく保持できればよい。stack。