動的計画法とは
解きたい問題
1本の水ようかんがある。
3つの切れ目が入っており、最大で4分割できる。
4分割した時の長さは順番にL_1、L_2、L_3、L_4(1<=L_i<=10, 1<=i<=4)で与えられる。
分割した後の長さがなるべく均等になるようにした時の、最大の長さと最小の長さの差を出力せよ。
ただし、最低1箇所は切るものとする
(日本情報オリンピック2017 予選問4 をベースにしたもの)
入力パターン
L_1～L_4 が
9
4
6
7
と与えられるとき。
(※) 総当たりで簡単にいけます(2番目の切れ目を切ればOK)が、動的計画法というものを理解したい点をご理解ください
現状の理解
動的計画法は、
- 前回の計算結果を、今回の計算に活かす。これを最終段階まで繰り返す
というのが、現状の私なりの理解(不足していると思うので、アドバイス大歓迎です)。
試したアプローチ
とりあえず、ゴールの一歩手前である
9
4
6
の段階での最適解を、次に活かすアプローチを考えた。
この場合は、
- 1番目の切れ目に切れば最小9、最大10。-> この時点での最適解！
- 2番目の切れ目を切れば最小6、最大13。
- 両方切れば最小4、最大9。
- 全部切らなければ最小19、最大19(ただし、最後で切ると最適でないのが自明なので除外)
筆者「なるほど、1番目の切れ目で切った結果を使いまわせばよいのか」。
で、最後のL_4
7
を考える。
L_3までの最適解にしたがって計算すると
- 3番目の切れ目を切れば最小7、最大10
- 3番目の切れ目を切らなければ最小9、最大17
差は3となる。
でも、これが答えかというと違ってて、L_3まででは最適でないケースだった
- 2番目の切れ目を切れば最小6、最大13。
の時に、
- 3番目の切れ目を切れば最小6、最大13
- 3番目の切れ目を切らなければ最小13、最大13
と、差が0となるケースが出る。途中段階の最適解を使いまわせないことになる。
質問事項
まとめると、
- 途中経過でずっと最適解と思っていたものが、以降の段階で覆される
というケースを、動的計画法の考え方でどう落とし込めばいいかがわからない。どう理解すればいいのでしょうか？
今回は4個のケースだったが、引用元の問題では最大50程度になる。
L_iの大きさも、最大1000程度までになる。
そうすると、49番目までずっと正解の切り方だったものが、最後の50番目で覆されるパターンも出てくる。
例えば、
1
:
(1 が 49個)
:
1
49
という感じのもの。
・ 49番目まで: 全ての切れ目で切る、が最適解
・ 最終段階: 最後の切れ目のみ切る、に最適解が変わる
これが理解できれば、動的計画法という得体の知れない魔物の攻略に、一歩近づくと思うのだが...
皆さんの知恵・経験をお貸しいただければと思います。