主題
題目連結：
題目意譯：
你被給定兩個索引值從 0 開始的整數陣列 nums 按 multipliers，大小依序是 n 和 m，其中 n ≧ m。
你一開始的分數值為 0。你想要執行恰好 m 次操作。在第 i 次操作中（索引值從 0 開始），你將：
選擇一整數 x，其位於 nums 的開頭或結尾。
將 multipliers[i] × x 加到你的分數值。
注意 multipliers[0] 代表著的是第一個操作、multipliers[1] 是第二個操作，以此類推。
把 x 從 nums 中移除。
回傳執行 m 次操作後的最大分數值。
限制：
n == nums.length
m == multipliers.length
1 ≦ m ≦ 300
m ≦ n ≦ 10 ^ 5
-1000 ≦ nums[i], multipliers[i] ≦ 1000
範例測資：
範例 1：
輸入： nums = [1,2,3], multipliers = [3,2,1]
輸出： 14
解釋： 一個最佳解為以下：
- 從結尾選，[1,2,3]，將 3 × 3 = 9 加到分數值中。
- 從結尾選，[1,2]，將 2 × 2 = 4 加到分數值中。
- 從結尾選，[1]，將 1 × 1 = 1 加到分數值中。
總分數為 9 + 4 + 1 = 14。
範例 2：
輸入： nums = [-5,-3,-3,-2,7,1], multipliers = [-10,-5,3,4,6]
輸出： 102
解釋： 一個最佳解為以下：
- 從開頭選，[-5,-3,-3,-2,7,1]，將 -5 × -10 = 50 加到分數值中。
- 從開頭選，[-3,-3,-2,7,1]，將 -3 × -5 = 15 加到分數值中。
- 從開頭選，[-3,-2,7,1]，將 -3 × 3 = -9 加到分數值中。
- 從結尾選，[-2,7,1]，將 1 × 4 = 4 加到分數值中。
- 從結尾選，[-2,7]，將 7 × 6 = 42 加到分數值中。
總分數為 50 - 15 - 9 - 4 - 42 = 102。
解題思維：
定義一個二維陣列 D，D[i][j] 代表在第 i 個（索引值從 0 開始）操作之後（含第 i 個本身）下且在前 i 次操作是挑前 j 個數字（因此剩下 i - j 次是挑尾端的）的情況下，你可以獲得的最大分數。
可以看到在有 j 次是挑前面的數字之情況下，nums 實際上只剩下 nums[j] ～ nums[n - (i - j) - 1] 這個子陣列之部分（畢竟根據定義：被挑到的數字會被移除）。
因此我們可以看到其遞迴式為
1. D[m][j] = 0、
2. D[i][j] = max(multipliers[i] × nums[j] + D[i + 1][j + 1], multipliers[i] × nums[n - (i - j) - 1]] + D[i + 1][j])
其中 1. 式是因為沒有操作可以執行了，因此其後可獲得分數當然為 0（因此其為遞迴停止條件）。
而 2. 式是在假設前 i 個操作有 j 次是挑前面（因此可以看到上式有額外條件：j ≦ i），因此我們會剩下 nums[j] ～ nums[n - (i - j) - 1] 這個部分，而此時根據定義：要嘛挑開頭（即 nums[j]）、要嘛挑結尾（即 nums[n - (i - j) - 1]）。
因此我們可以看到 D[0][0] 最後應儲存著所求。
所以我們現在有兩種方式可以解此問題，一種是直接遞迴求解（Top-down，如這題）、另一種是從已知推出未知（Bottom-up）。而由於範例程式碼是採取 bottom-up，因此這邊以此方向說明：
首先，我們知道什麼？根據遞迴式是只要 i = m，D[i][j] 之值即為 0。
因此可以看到 i = m - 1 應為下一個可以推得的目標。因為其他 i 值根據遞迴式都需要仰賴著第 i + 1 ~ m - 1 次操作之最佳解，而 i = m - 1 本身只需要考慮自己而已。
以 nums = [1,2,3,4,5] 、 multipliers = [6,7,8] 為例：
i = 2 時，nums 的剩餘部分可以為以下三種：
[1,2,3]、
[2,3,4]、
[3,4,5]
其依序對應著 j = 0 、 j = 1 和 j = 2 之情況。
而挑完最後一個數字就結束了。因此承上例（記得 multipliers[2] == 8）：
D[2][0] 之值為 max(8 × nums[0], 8 × nums[5 - (2 - 0) - 1]（即 nums[2]，以下直接寫結果之索引值）)、
D[2][1] 之值為 max(8 × nums[1], 8 × nums[3])、
D[2][2] 之值為 max(8 × nums[2], 8 × nums[4])
所以我們就求完了 i = m - 1，所以可以推得 i = m - 2 的情況。同樣承上例（multipliers[1] == 7）：
D[1][0] 之值為 max(7 × nums[0] + D[2][1], 7 × nums[3] + D[2][0])、
D[1][1] 之值為 max(7 × nums[1] + D[2][2], 7 × nums[4] + D[2][1])、
再繼續同一個例子（multipliers[0] == 6）：
D[0][0] 之值為 max(6 × nums[0] + D[1][1], 6 × nums[4] + D[1][0])
所以把 nums 中對應的數字全部代進去，可以看到這個例子的最佳分數為 6 × 5 + 7 × 4 + 8 × 3 = 82。
而其他 nums 、 multipliers 之情況也與上同理，只要從 i = m - 1 往回推即可。時間複雜度 O(m ^ 2)。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
