動的計画法とは

解きたい問題

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番目まで: 全ての切れ目で切る、が最適解
　・ 最終段階: 最後の切れ目のみ切る、に最適解が変わる

これが理解できれば、動的計画法という得体の知れない魔物の攻略に、一歩近づくと思うのだが...

皆さんの知恵・経験をお貸しいただければと思います。