動的計画法とは

解きたい問題

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番目の切れ目で切った結果を使いまわせばよいのか」。

で、最後のL_4

7

を考える。

L_3までの最適解にしたがって計算すると

差は3となる。

でも、これが答えかというと違ってて、L_3まででは最適でないケースだった

の時に、

と、差が0となるケースが出る。途中段階の最適解を使いまわせないことになる。

まとめると、

というケースを、動的計画法の考え方でどう落とし込めばいいかがわからない。どう理解すればいいのでしょうか？

今回は4個のケースだったが、引用元の問題では最大50程度になる。

L_iの大きさも、最大1000程度までになる。

そうすると、49番目までずっと正解の切り方だったものが、最後の50番目で覆されるパターンも出てくる。

例えば、

1
:
(1 が 49個)
:
1
49

という感じのもの。

　・ 49番目まで: 全ての切れ目で切る、が最適解
　・最終段階: 最後の切れ目のみ切る、に最適解が変わる

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

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