動的計画法を用いるアルゴリズムの開発

寝る前に頑張って説明してみよう。

例えば、15,3,7,6,10,4,13,2,3,6　という１０個の数に、
区切りを３つ入れる場合について考えてみます。
この場合、下の図のようなテーブルをプログラムで作成すればいいわけです。
（等幅で見てね）

15 3 7 6 10 4 13 2 3 6
区切り残り０：10,69 9,54 8,51 7,44 6,38 5,28 4,24 3,11 2, 9 1, 6
区切り残り１： 4,38 4,28 4,27 3,24 2,24 2,17 1,13 2, 6 1, 6 1, 6
区切り残り２： 3,25 2,24 3,23 2,17 2,14 1,13 1,13 1, 6 1, 6 1, 6
区切り残り３： 2,23 3,16 2,14 1,14 1,13 1,13 1,13 1, 6 1, 6 1, 6

例えば左下の(2,23)が何を表しているかというと、
「区切りがまだ３つ使える場合、
　　次の最適な区切りはここから２つ目の場所、
　　その場合の最大値は23になりますよ」
という事です。すなわち、１つ目のグループは[15,3]が正解だと解るわけです

これがわかれば、問題は、
「7,6,10,4,13,2,3,6　という８個の数に区切りを２つ入れる」
という風に変わります。
その場合は(3,23)、すなわち２つ目のグループは[7,6,10]とわかります。

このように追っていくと、答えは[15,3]、[7,6,10]、[4,13]、[2,3,6]となります。
（続く）

さて、このような表をどうつくるかという問題ですが、
それは自分で考えてください。

ヒントは、
・区切り残り０の場合は単純計算です。
・区切り残りＮの場合が解っていれば、Ｎ＋１の場合もわかります。

例：（等幅）
区切り残り４： 1,16 1,14 2,13 1,13 1,13 1,13 1,13 1, 6 1, 6 1, 6

数学的帰納法により、全ての場合の表が求まります。

わかりにくいかもしれませんが、もし動的計画法の知識があれば、
割合すんなりと読めるのではないでしょうか？甘い？>>1さん