題目連結：
題目意譯：
你被給定 n 顆氣球，其編號為 0 到 n - 1。每顆氣球上面塗著一個數字，並以一陣列 nums 表示。你被要求打破所有的氣球。
如果你打破了第 i 顆氣球，你將得到 nums[i - 1] × nums[i] × nums[i + 1] 個金幣。如果 i - 1 或是 i + 1 超出了陣列的邊界，則將其視為上頭塗著 1 的氣球來對待。
回傳藉由明智地打破氣球，你可以獲得的最大金幣數。
限制：
n == nums.length
1 ≦ n ≦ 300
0 ≦ nums[i] ≦ 100
範例測資：
範例 1：
輸入： nums = [3,1,5,8]
輸出： 167
解釋：
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
金幣 = 3×1×5 + 3×5×8 + 1×3×8 + 1×8×1 = 167
範例 2：
輸入： nums = [1,5]
輸出： 10
解題思維：
本題跟求最佳的矩陣乘法順序（如這題）相似：
假設我們已知所有子問題的最佳解，即對於任意一個子問題 D[L][R]（代表要打破第 L ～ R 顆氣球），我們都知道以最佳的順序得到的最大分數值。則我們的主問題的最大分數（以及打破的順序）便可以藉由窮舉第一顆氣球要打破誰來判斷，即 D[0][n - 1] 最大分數值為
max(D[0][i - 1] + D[i + 1][n - 1] + 打破第 i 顆氣球的分數)
其中 0 ≦ i < n。不過這邊省略了一些邊界條件，例如說當 i = 0 時，沒有前面那個 D[0][i - 1] 之項次等等。這邊交給讀者自行補全（或是直接參見範例程式碼）。
所以我們得到了一個類似於矩陣乘法的遞迴式，所以可以仿照該題（或是像不少動態規劃（Dynamic Programming）的題型一般）的 bottom-up（參見註 1）方式來求得主問題 D[0][n - 1]，即所求。
不過，我們其實也可以按照 top-down（參見註 1）來求得 D[0][n - 1]——也就是真的利用深度優先搜尋（Depth First Search，DFS）的方式來求出遞迴式的值。
當然，這將面臨到一個問題，也就是我們將重複計算大量的相同子問題（尤其是越小的子問題）。而這很好解決，不要重複計算即可，即把已經算過的子問題之答案存起來便可。之後碰到相同的子問題，直接去看答案就好。
註 1：bottom-up 在這邊指的是「先得到小問題之解答，再來拼湊出大問題之解答」的概念；相對地，top-down 指的則是「大問題拆成若干個小問題各自去解，再拼湊成原本的答案」的概念。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
