先把之前的筆記隨意複製貼上...
明天一定會改的 吧

最簡單的 DP：fibonacci 數列

只要能用到上一個結果，就算只有三個變數的費氏數列，也算是 dp。

01 背包問題（Knapsack）

01 的意思就是要馬不放，要馬放。
背包有一定容量，而每個物品有各自的體積和價值，
想要問某個背包容量下，總價值最大是多少？

這個問題如果發生在生活中，
一般人都會想著，先把 CP 值高的東西趕快塞一塞再說！
然而如果沒辦法有效利用剩餘的空間，這或許並不是最佳解。

利用 DP，每個物品可以選擇放與不放，每次更新就是取大的。

啊..到底為什麼會講到這邊，三百字啊三百字...orz

Kadane: 找出最大 subarray

找出最大 subarray 除了可以單獨出題 53. Maximum Subarray
也可能是其他問題的其中一環，忘記哪題了。

以下稍微紀錄一下思考 DP 的過程，
有時候一開始定義的 DP 並不可行，
後來才會發現並做更動，
而這些最後都會轉化成經驗～變成下次定義 DP 時比較容易往正確方向走

• base case
  可以知道 到 0 的 maxsubarray 一定是 nums[0]

• 嘗試定義 dp[i] 為 從 0 到 i 的 max subarray

舉例試試，
若要知道 [0:1] 的 max subarray，需考慮：

1. nums[0]：曾經的的 dp 結果
2. nums[0] + nums[1]：曾經的 dp + 新值
3. nums[1]：新值
   從此好像能得出 dp[i] = max(dp[i-1], dp[i-1] + nums[i], nums[i])，
   這樣得到的數值，雖然目前的答案是對的，但並不知道是否含有 nums[i]，而無法推得下一個 dp 結果。
   為了求下一個 dp[i+1]，我們需要知道 nums[i] 是否包含，因為 subarray 是需要連在一起的。

因此重新定義 dp[i] 為 ==以 nums[i]結尾== 的 maxsubarray