主題
題目連結：
題目意譯：
你目前正在設計一個動態陣列。你被給定一個索引值從 0 開始整數陣列 nums，其中 nums[i] 為在時間點 i 時陣列中會有的元素數量。除此之外，你同時也被給定一個整數 k，其代表著你可以調整陣列的大小之次數（可以選定任意大小）。
在時間點 t 時陣列的大小 sizet 至少應 nums[t] 因為陣列需要有足夠空間來容納所有元素。在時間點 t 時浪費的空間定義為 sizet - nums[t]，而浪費空間總計為每一個時間點 t 時浪費的空間之總和，其中 0 ≦ t < nums.length。
回傳在你可以調整陣列的大小最多 k 次的情況下最小浪費的空間總計。
注：一開始的陣列大小可以是任意大小，而且不會計入調整陣列大小的次數。
限制：
1 ≦ nums.length ≦ 200
1 ≦ nums[i] ≦ 10 ^ 6
0 ≦ k ≦ nums.length - 1
範例測資：
範例 1：
輸入： nums = [10,20], k = 0
輸出： 10
解釋： size = [20,20].
我們可以設定一開始的大小為 20。
浪費的空間總計為 (20 - 10) + (20 - 20) = 10。
範例 2：
輸入： nums = [10,20,30], k = 1
輸出： 10
解釋： size = [20,20,30].
我們可以設定一開始的大小為 20 並且在時間點 2 時調整為 30。
浪費的空間總計為 (20 - 10) + (20 - 20) + (30 - 30) = 10。
範例 3：
輸入： nums = [10,20,15,30,20], k = 2
輸出： 15
解釋： size = [10,20,20,30,30].
我們可以設定一開始的大小為 20，並且在時間點 1 時調整為 20 以及時間點 3 時調整為 30。
浪費的空間總計為 (10 - 10) + (20 - 20) + (20 - 15) + (30 - 30) + (30 - 20) = 15。
解題思維：
可以用動態規劃（Dynamic Programming，DP）的精神來解。
定義一個二維陣列 D，其中 D[i][j] 代表著在調整大小 j 次的情況下只考慮前 i 個時間點所浪費的空間最小為多少。
可以看到遞迴式為：
D[0][j] = 0，其中 0 ≦ j ≦ k；
D[i][0] = M × i - S，其中 0 ≦ i ≦ nums.length 、 M 為 max(nums[0], nums[1], ……, nums[i - 1]) 而 S 為 nums[0] + nums[1] + …… + nums[i - 1]。因為每一個時刻都必須能裝下所有元素，因此一開始的大小要設成前 i 個時間點元素最多的時候；
D[i][j] = min(D[x - 1]][j - 1] + Wx)，其中 1 ≦ x ≦ i 、 Wx = Mx × (i - x + 1) + Sx 且 Mx = max(nums[x - 1], nums[x], ……, nums[i]) 、 Sx = nums[x - 1] + nums[x] + …… + nums[i]。與上同理，只是現在由於我們可以調整大?。ㄗ⒁馕覀兛梢浴咐速M」調整大小的次數），所以可以看做是窮舉 x 作為新的開始。
最後的答案將落在 D[nums.length][k]。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
