動的計画法がわからない
e869120さんのこの記事を参考に勉強していて動的計画法のところで思い切りつまずいている茶色コーダーです。割とA~Dの4完までは安定してきたのですが、E問題を時間内に解けたことはなく、DPが出てきたらその時点で詰みという状態です。ABCのE問題辺りで出てくるのは2次元以上のDPであり、手も足も出ない。しかし出題率は高く、上記記事の精選100問のうちでも、DP関連は19問といかに避けて通れないかということがわかります。また、この記事を書いた時点(2020/11/21)直近5回でのABC-EとFでのDPが解放の問題は5問と相当の出現率です（さすがにこのペースが続くとは思いませんが）
ただ、習うより慣れろの精神で解こうとするも全く成長しない。解法が見えてこない。何食べればあんなの解けるんだ？コツと書いていますが、現在は何がわからないのかを書くことしかできない状態で、これからアップデートしていきたいと思います。
今わかってきたこと
DPまとめコンテストについては何回か解法見ながら解いているため、E問題までは解ける。ただし、応用力がないため、1次元DPすら怪しい。そう、1次元DPすら怪しいのである。フィボナッチ解いていきなりナップザックDPということ自体、相当なスペックがないと不可能かと思います。そういった意味ではDPまとめコンテストC問題は橋渡しぽいのですが、それ以前にまずは1次元DPを極める（ある問題一通り解く）方がよい気がします。
①AOJ ALDS_10_A – フィボナッチ数
②Atcoder DPまとめコンテスト A Frog1
③Atcoder DPまとめコンテスト B Frog2
④AOJ DPL_1_Aコイン問題
⑤ABC 099C – Strange Bank
⑥ABC 129C – Typical Stairs
⑦AOJ 0168 観音堂
DPを解くコツとしてネット徘徊した感じでは
①遷移を考える。
②まず全探索を考えてそれをDPにする。
ということがよく書かれています。おそらく間違っていないのですが、理解できていないです。
今わからないこと
DPでは数え上げの問題が多いが数え上げ方がそもそもわからないことが多い。これが結構いたい。遷移を考える以前の問題で、DPで解く必要がなくても解けない可能性がある（まずはここも勉強する）
2次元以上の遷移、というか1次元すら怪しい。上記7問を解く（解いたはずなのになにぶん記憶力が落ちてきているのか、え？解いたっけというレベルで解法を忘れている。おそらく本質的な理解に至っていないため。わかっていない部分洗い出すためにもまたやってみる）
コメント