前回のDPの問題について
前回のブログでわからないとか言ってた自分ですが、ついに第二の神が現れました！
正直再帰DPの流れちゃんと追えてないんですが…return dp[n] = dp(〜〜)...のところで再帰して一気に一番最後の方まで進んじゃうじゃないですか。でそこまでのcostが加算された値が奥のほうのDPテーブルに入っちゃうわけですが、その経路が最短かはまだ確定してない（続
— htkb (@htkb_) June 4, 2017
ですよね？なのにdpテーブルに書き込まれたら再計算はしない（dp[n]に値があったらすぐreturnしてる）ので、最短ではないコストが書き込まれていってしまうんだと思います。説明下手でわけわかめでごめんなさい＞＜AC→https://t.co/NHOziAYEls
— htkb (@htkb_) June 4, 2017
htkbさん、最後まで本当に有難うございます。
これからまとめていきます。
前回やらかした点について
僕の前回のコードは、はじめに探索した結果だけをdpテーブルに代入するという結果になってました。。
Submission #1322248 - AtCoder Beginner Contest 040 | AtCoder
このコードの場合、すべて一つ飛ばしでいれたときの場合にdpテーブルに代入するという形になっています。
しかしそれだと最小値は求めることができません（全探索どころかほとんど探索できていないから）
それを解決及び理解するために
自分が理解するのにつっかかった点を挙げておきます
- 関数が一回呼ばれるごとに、dp[num]に数値が代入される
- たとえそこまでの行き方が何通りあろうとも、numはnumで一つ（日本語力）
- こういう場合、合計で見てしまっては全体を見るために二つの値では比較できないので、最後から徐々にのぼっていく感じでreturn文で返す。
こんな感じですね。これが自分の間違いです。
こんな考え方で差分のみをとって比較、そして返すを繰り返し、return文ではcostが足されて帰ってくるので、これでACできます。
ちなみにこの写真がもっとも分かりやすいかと
考えのお手伝いになれば幸いです pic.twitter.com/XkhqEz0XQ4
— htkb (@htkb_) June 4, 2017
htkbさん神です。debugの仕方も最高にうまいです。勉強になります。
ただ、htkbさんによるとこの写真はもしかしたら間違いが含まれているかもしれませんがそこのところはご了承ください、だそうです（いや、間違い多分ないけど、htkbさんプロだし）
最後に
コードは自分で明日書いてみます。
深さ優先探索みたいな感じでDPをするときは、最初にたどり着いたところで代入すると間違えますね。
returnするときにどんどん足していって、解を出すことが必要ですね。
このこと知れてよかったとか思う問題でした。
forで解いた方が簡単かもなぁ
