(ΦωΦ)＜あとがき
まず1ページめ(01ナップサックのやつ)で、解けた！と思ってもらおうとしてます。達成感を味わってもらおうと思いました。
あとはやっぱり問題を解いてこそだと思うので、どんどん解いてもらうようにしてます。
練習問題は先に取りあげたやつの類題っぽいのを選んで、おんなじようにやってみてね、という感じです。
DPが超苦手な人はたぶん全探索が苦手です。
なので今回はわりと全探索を書かせようとしてます。
選んだ問題の中にはO(1)で解けるのもあったりして、そういう解き方は魅力的です。
しかし今回は、その解き方に気付くために全探索やDPで実験できるようになろうぜ、という意図で書きました。
昔のあたしならO(1)の解法だけ覚えてたと思いますが、最近は基本(要するに探索)が大事だと思ってます。
今回の対策講座をやったからといって、すぐに動的計画法の問題が解けるようになるわけではないはずです。
一朝一夕で身についてたら全員が出来てるわけで、そうじゃないからこそ日々の訓練が必要なんでしょう。
今回、DPの記事を書いてあたし自身が非常に勉強になりました。記事を書けば勉強になるなと再認識しています。
みなさんも人に伝える意図で記事を書きましょう。
これでようやく動的計画法が苦手な人が、動的計画法が超苦手な人へアドバイスしてみるが読めるレベルになったと思ってます。
折しもGrenacheさんのところが丁寧なDPの記事を書かれています。扱ってる問題は難しめですが、こちらも是非。
(ΦωΦ)＜おしまい。明日は@hadroriさんです。お楽しみに！