課程資訊
此為Alphacamp的Leetcode訓練營課程，內文僅為個人心得。
Dynamic Programming
- 將大問題拆成小問題，並且將小問題的答案儲存起來隨時取用，以減少再次計算需要的時間。
- Dynamic：意指根據需求去動態規劃貯存答案的空間長度，而非固定長度
例子-費式數列
- Fibonacci：0, 1, 1, 2, 3, 5 ...
- Top-Down：將大問題拆解成小問題，逐步逼近答案
- Bottom-Up：由小問題組成大問題，逐步逼近答案
- 優化-減少空間使用 Big O(1)；缺點是過程中不取得長度為 n 的費式數列的資料，若不需要儲存資料時可考慮使用。
適用情境
- 重複的子問題
- 子問題具有最佳解
- 子結構最佳解一旦確定即不再改變
53. Maximum Subarray
題目敘述：
給予一個沒有排序的陣列，元素是整數，有負數有正數，求最大的連續元素總和。
例子：
[-2,1,-3,4,-1,2,1,-5,4] => 最大連續數字的總合為6，[4,-1,2,1]解法：
解法1，暴力解，把所有可能的連續陣列取出做比較
解法2，動態規劃，從陣列index 0 開始迭代，把目前累計的值加上目前迭代的對象與迭代對象取最大值，並把迭代過程中最大值紀錄或存在原本陣列上
解法3，二分法，將陣列分成左右兩半，則最大連續陣列出現的位置有三種：
- 在左側
- 在右側
- 在中間，被分割兩半
所以需要找到左側、右側連續和最大值與中間左右兩邊和的最大值
參考
53.maximum-sum-subarray-en.md
[LeetCode] 53. Maximum Subarray 最大子数组
518. Coin Change 2
題目敘述：
給予一個整數amount、陣列coins代表金額與可以使用的硬幣面額，求可以組出amount的硬幣組合
例子：
amount 5、coins:[1,2,5]
則組合有4種
[5]
[2+2+1]
[2+1+1+1+1]
[1+1+1+1+1+1]
解法：
邏輯：
用一個amount+1長度的陣列來記錄結果，key代表各種amount的值，value代表組合該amount能用各coins組出來的種類;而amount=0時只有一種組合(什麼都不做)
以change(6,[2])來說，陣列的結果會如下
key [0][1][2][3][4][5][6]
value [1][0][1][0][1][0][1]- amount=2時，可以用1個2組出
- 當amount=4時，前面已經知道2能用1個2組出了，剩下的值(4–2) = 2 可以用2+2來組出
- 當amount=6時，已經知道有4可以使用，剩下的值(6–4)=2可以用4+2來組出
- 其他的值以此類推，最後回傳目標的amount即所求
1143. Longest Common Subsequence
題目敘述：
給予兩個字串，求由左到右順序最大相同字母排列的長度
例子：
Input: text1 = "xabccde", text2 = "ace"
Output: 3text1跟text2有最大相同長度字母ace
思考：
以Dynamic來解題，先將題目拆解成小題目：
先比較xabccde跟a;由x、xa、xab、xabc、xabcc、xabccd、xabccde跟a比較，並記錄最大長度
[-][-][x][a][b][c][c][d][e]
[-][0][0][0][0][0][0][0][0]
[a][0][0][1][1][1][1][1][1]接著比較xabccde跟ac;由x、xa、xab、xabc、xabcc、xabccd、xabccde跟ac比較，記錄最大長度
[-][-][x][a][b][c][c][d][e]
[-][0][0][0][0][0][0][0][0]
[a][0][0][1][1][1][1][1][1]
[c][0][0][1][1][2][2][2][2]可以看到一個規律，當比較的兩個對象不相同時，最大長度是之前共有的最大長度，反之，則是不包含這兩個對象的最大長度 + 目前比較對象的長度(也就是1)
ac跟xa比較，得到1，這個是由前面a比較xa的結果而來
[-][-][x][a]
[-][0][0][0]
[a][0][0][1]
[c][0][0][1]xabc跟ac比較，兩者都有相同的c，所以找xab、a之間最大長度，也就是2的對角線上的1
[-][-][x][a][b][c]
[-][0][0][0][0][0]
[a][0][0][1][1][1]
[c][0][0][1][1][2]
根據這個方式逐一比較，最後取得最後一筆結果
[-][-][x][a][b][c][c][d][e]
[-][0][0][0][0][0][0][0][0]
[a][0][0][1][1][1][1][1][1]
[c][0][0][1][1][2][2][2][2]
[e][0][0][1][1][2][2][2][3]解法：
二維陣列
單一陣列