【LeetCode】Dynamic Programming II

先把之前的笔记随意复制贴上...
明天一定会改的 吧

最简单的 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