題目連結：
題目大意：
輸入第一列給定一正整數 N （1 ≦ N ≦ 1000），代表有一棵樹有 N 枝樹枝（可以視為圖論中圖的「節點」），每枝樹枝有一個「枯枝值」。接著的第二列給定 N 個非負整數，代表這棵樹根據前序探訪（Preorder Traversal，這題有介紹）後所產生的枯枝值序列。
此時，我們定義整棵樹的枯枝程度為
max(左子樹枯枝程度, 右子樹枯枝程度) + 根節點（樹枝）枯枝值
其中，如果有樹枝沒有左子樹或是右子樹則將對應的枯枝程度之值視為 0 。
試問根據給定前序探訪之枯枝值序列，在所有我們可以還原出的樹中，最小以及最大的枯枝程度之值為何？
範例輸入：
範例輸入 #1
3
1 2 0
範例輸入 #2
7
3 1 1 0 2 0 5
範例輸入 #3
10
1 2 3 0 2 3 3 0 2 5
範例輸出：
範例輸出 #1
3 3
範例輸出 #2
8 12
範例輸出 #3
6 21
解題思維：
可以看到，當所有樹枝只有左子樹或是右子樹時，根樹枝的枯枝程度即是全部樹枝的枯枝值之總和。因此枯枝值總和即是最大的枯枝程度。
而我們定義 D[i][j] 為序列中第 i ～ 第 j 個樹枝（方便起見，這邊統一 i < j，且索引值從 0 開始）所能形成的最小枯枝程度，則我們可以看到
當 i = j 時，D[i][j] = 第 i 根樹枝的枯枝值；
當 i = j - 1 時，D[i][j] = 第 i 根以及第 j 根樹枝的枯枝值總和；
除上之外的情況為，D[i][j] = D[i][i] + min(max(D[i+1][k], D[k+1][j])，i+1 ≦ k < j)
可以看到上面的第三種情況有點類似於最佳矩陣相乘，例如這題。因此作法可以參見該題的求法，一步步求出各個數對 (i, j) 的 D[i][j] 值。
而所求的最小枯枝程度即是 D[0][N - 1]。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
