【27日目】今日からDP
良問100選もやっと3分の1まで来た。まだまだ先は長いが気を引き締めて頑張らねば。
今日からしばらく(No. 34 ~ 52)動的計画法(DP)が続く。これはグラフの次に苦手なのでしっかり押さえておきたい。。グラフと違って好きなのは好きなのだが、どう置けばよいのか分からずいつも苦戦する。
まずは基本から。
34 ALDS_10_A - フィボナッチ数
これはさすがにできる。
35 DPL_1_B - 0,1ナップザック問題
超定番ナップザック。もう何度もやっているので流石にこれもできるが、一から独力で思いつくか、と言われると何とも自信ない(え)。
36 DPL_1_C - ナップザック問題
ちょっと一捻りしたナップザック。この時点で若干苦戦気味(やばいね)。漸化式を少し変えないとTLEになる。式とにらめっこして計算の無駄を探して、という作業。
37 DPL_1_A - コイン問題 基本問題です。
ナップザックの亜種。これもできる。
38 ALDS_10_C - 最長共通部分列
LCS。最初は漸化式見ても何でそれでいいのか今一つピンとこなかったけれど、もうそろそろ慣れた。
今日39の途中までやったので、明日はその続きから。DPは漸化式さえ思いつけば実装はそこまで難しくないから頑張っていこう。
