主題
題目連結：
題目大意：
輸入有多筆測試資料，每筆佔三列。
測資第一列給定一正整數 L （L < 100 ， 當 L ＝ 0 時代表輸入結束），代表木頭的原長度。第二列給定一整數 N （N < 50），代表木頭的切割點之數目。第三列則給定 N 個正整數 C （0 < C < L），代表切割點的位置（由小排到大，且皆相異）。
因為每次切割木頭的成本是要切割的木頭之長度，因此欲切割位置的先後順序會影響總成本。
例如 L ＝ 10 ， C ＝ 2 、 4 、 7 。如果按照 2 、 4 、 7 的順序切，則每次切割的木頭片段之長度分別為 10 、 8 、 6 ，因此總成本為 10 + 8 + 6 ＝ 24 ；但是如果按照 4 、 2 、 7 的順序，則木頭片段長度分別為 10 、 4 、 6，總成本為 10 + 4 + 6 ＝ 20 。
試問最小的切割成本為何？輸出格式參見範例輸出。
範例輸入：
100
3
25 50 75
10
4
4 5 7 8
0
範例輸出：
The minimum cutting is 200.
The minimum cutting is 22.
解題思維：
將木頭的頭尾也當作切割點，即 C ＝ 0 以及 L 。並加入原本的 N 個 C 值裡並重新命名為 C0 、 C1 、 …… 、 CN+1 。
定義一個二維矩陣 Di, j （0 ≦ i ≦ j ≦ L），代表考慮進 Ci+1 ～ Cj-1 這些切割點的最小切割成本（如果 i < j - 1 的話，至於 i ≦ j 的話，初始化為 0）。因此可以看到我們的所求即是 D0, N+1 。
而 Di, j 之遞迴式為：
i ≦ j ， Di, j ＝ 0
i < j - 1 ， Di, j ＝ min(Di, k + Dk, j + Cj - Ci)，其中 i < k < j 。
對於上式的理解，可以參見最佳矩陣乘法那一題的圖解，其遞迴式也是類似上面的形式。
因此，我們可以先窮舉一個步伐長度值 s ，從 2 開始到 N + 1。然後讓 i 從 0 開始跑，跑到 N - S + 1 為止，每個 i 值代表著現在要求 Di, i+s 的最小成本。
此時，照著遞迴式窮舉 k 值即可，因為我們對於每個 s 值，前面的所有 i ＝ j - s + 1 的 Di, j 之值已知。而現在要求的就是 i ＝ j - s 的那些 Di, j 之值。因此，整體架構是一個三層迴圈，正如同矩陣乘法那一題一樣。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
