動的計画法

[strass]

情報オリンピック予選通過には4問目を解くための必需品として、動的計画法が存在しているのだと知りました
動的計画法は、なんとなく知ってはいて、0-1ナップザック等書いたこともありますが、実際に過去の４問目をやっても全く太刀打ちできませんでした

慣れている方に質問ですが、正直「型」に慣れて書いている感じでしょうか？
いや、もちろんそうだと思うんですが、
例えば、慣れても毎回表を作って考えるものなんでしょうか

初心者の段階から、問題で利用できるようなレベルになるには、
どんな流れが必要だろうかと考えてます

問題こなしなさい、という方は情報オリンピックの４問目レベルに対応できるようなモノで、
いい例があったらぜひ教えていただきたいです

[みけCAT]

動的計画法が難しいと思うならば、使わなければいいと思います。
たまに動的計画法でないとメモリやスタック(再帰の深さ)が足りなくなる問題もありますが、
情報オリンピック予選の4問目レベルならメモ化探索で解けるはずです。

[strass]

そうなんですね！
確かに、計算量なら同程度の枠組みだし、本番まで時間もない中、
何もDPにこだわる必要はなかったですね

今からメモ化再帰をできる限りモノにしたいと思います
的確なアドバイスありがとうございました