Dynamic programming

http://blog.csdn.net/linhuanmars/article/details/38468361

DP:
1.状态:即定义,中间的状态
 2.方程:即从前一种状态推出现在的状态.
 3.初始化:极限小的状态,即为起点.
 4.答案:终点

 递归：
 1. 定义（状态）
    • 接受什么参数
    • 做了什么事
    • 返回什么值
 2. 拆解（方程）
    • 如何将参数变小
 3. 出口（初始化）
    • 什么时候可以直接 return

坐标型  20%
序列型  20%
划分型  20%
区间型  15%
背包型  10%
拓扑型  5%
博弈型  5%
综合型  5%

state machine

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/

坐标型 20%

f[i] 第i个

https://leetcode.com/problems/word-break/description/ https://leetcode.com/problems/concatenated-words/description/ https://leetcode.com/problems/unique-paths/

Divide & conquer, solve with 2 pass: order and reversed order https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/description/ https://leetcode.com/problems/bomb-enemy https://leetcode.com/problems/maximum-sum-of-3-non-overlapping-subarrays/description/

LIS problem https://leetcode.com/problems/longest-increasing-subsequence https://leetcode.com/problems/russian-doll-envelopes/description/ https://leetcode.com/problems/increasing-triplet-subsequence https://leetcode.com/problems/maximum-length-of-pair-chain https://leetcode.com/problems/number-of-longest-increasing-subsequence https://leetcode.com/problems/increasing-subsequences/description/ https://leetcode.com/problems/longest-continuous-increasing-subsequence/description/

序列型 20%

f[i] 前i个

can be O(1) variable or O(n)/1D variable

these problems are conditional, discuss different situation:

https://leetcode.com/problems/paint-fence/description/ https://leetcode.com/problems/paint-house/description/ https://leetcode.com/problems/paint-house-ii/description/ https://leetcode.com/problems/maximum-vacation-days/description/ https://leetcode.com/problems/house-robber/ https://leetcode.com/problems/house-robber-ii/description/ https://leetcode.com/problems/climbing-stairs/ https://leetcode.com/problems/maximum-subarray/description/

局部最优和全局最优 https://leetcode.com/problems/maximum-product-subarray/description/ https://leetcode.com/problems/maximum-subarray

Stocks: the whole series key point: buy and sell must cannot happen together, because if price go down, it's buy point, selling here get 0 profit, meaningless. if price go up, it's sell point, won't buy. buy2 must happen before sell1, because if not, buy2 will be negative, won't update.

buy1 = Math.max(buy1, -prices[i]);
sell1 = Math.max(sell1, buy1 + prices[i]);
buy2 = Math.max(buy2, sell1 - prices[i]);
sell2 = Math.max(sell2, buy2 + prices[i]);

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/ https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/description/ https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/