yukicoder No.134 走れ!サブローくん
abst
今回は、bitDPの練習でyukicoderの「走れ!サブローくん」をpythonでときました。 No.134 走れ!サブロー君 - yukicoder
解法
bitDPでの巡回セールスマン問題
ポイントは DP配列を二次元 にして、dp[すでに下ろした荷物][最後に訪問した場所]とすること。
(コストの計算に、距離が関わってくるため、次に訪問する場所と最後に訪問した場所のマンハッタン距離を計算する必要がから、 最後に訪問した場所を覚えておく!
提出with python
終わりに
DP苦手なので解けるようになりたい。 あと、暇だったら他の種類のDPもやる。
参考にしたサイト
ここにbitDPの問題 まとめてあって、ありがたい! www.hamayanhamayan.com