今日の学習

一昨日のABCで蟻本いよいよちゃんとやるぞの思いを強くしました。
やります。

進捗と感想

蟻本P55まで。
DPの復習。
ときおり見直さないといろいろ忘れている。
EDPC D問題の典型ナップサックをいろいろな解き方で解きました。
D - Knapsack 1

再帰か配るDPがわかりやすそう。

メモ化再帰

　今日のWAから
　×　return res=dp[i][j];
　○　return dp[i][j]=res;

　resの値をdpテーブルにメモしてリターンする場合の書き方です。
　分けて書くなら
　　dp[i][j]=res;
return res;
　となるので下が正しいのですがresを返す気持ちが先走り上のような書き方でWAになりました。
　上の書き方だとからっぽのdp[i][j]の内容がresに入ってリターンされるのでdpの初期値が返されてしまいます。

memset

直接メモリに書き込んで初期化するようで1byte単位なので0埋めか-1埋めには適しているけれど1埋めなどには向かない。-1埋めで使えるのは全桁が1なので。

memset(dp,-1,sizeof(dp));

メモ化再帰につかうdpテーブルの初期化は-1で初期化するのが本来かもしれないけど0で初期化し0より大きいときにメモ化値を使うようにしても速度などは変らないのでmemsetで初期化しなくてもdpの宣言をグローバルにおいてやれば十分そう。