DP Pattern
1. Update in push style
主动把答案推给大规模的母问题(因为之后就会用到)
比较贴近Bottom-up 思想
2. Update in pull style
从较小规模的子问题拉答案过来。
比较贴近Top-down 思想
===================================================
用 BM投票算法 找 众数 (同意票，否定票，可以互抵销，最后留着的是众数)
===================================================
Find pattern in string s
KMP algorithm
BM algorithm
Z algorithm
prefix, suffix
===================================================
用 Floyd alogithm 找 Cycle in linked list ( 双指针 + 快慢指针，快的会追上慢的 )
用 Coloring algorithm 找 Cycle in graph ( 遇到同颜色的就是有Cycle)_
用 Coloring algorithm 检查 bipartite (相邻两个点必须著不同颜色)
用 Coloring algorithm 找 一笔画到终点的相依路径
<-> 等价 Topological sort by dergee (in-degree少的先做，因为限制较少)
===================================================
DFS 配 Stack or recursion (Last In First Out)
BFS 配 Queue or priorty queue ( First in First out, Best pop out)
用 DFS 看 路径存在性
<-> 等价可用 BFS 看 路径存在性
局部加速技巧: 双向BFS (从起点、终点同时出发，如果中间某处相遇，代表有路径抵达)
用 BFS 找拜访所有节点的最短路径 (with bit flag on node visited state)
用 DFS + DP 看燃料耗尽前的所有漫游路径
用 DFS 找连通元件 Connected component
<-> 等价 BFS 找法
<-> 进阶 Union-Find disjoint set (快速合并, with path compression)
用 DFS 找树高 <=> 用 BFS 找最浅的叶子、最深的叶子
用 DFS 看 maze problem (固定探索规则探索整张图)
用 DFS 看 Flood fill (绘图软件中的颜料桶整块着色的功能)
用 DFS 看 递增序列、递减序列 (爬山 下山，数字类比成海拔高度。)
用 BFS 看 level-order traversal
用 BFS 判断是否为Complete tree (中间不可有Null node，因为必须Leftward-compact1)
用 BFS 看 等权图中的Shortest path (依赖刚刚由内往外"逐层"探索的性质)
用 特化过的BFS (Greedy + Priorty queue) 看 Shortest path by Dijkstra
用 三角关系看 Relaxation ( 借由中间节点v更新 dist[u] = dist[v] + cost[v, u] )
用 Floyd-warshall 看 All pair shortest path
(更好的路经，依赖已知的路径去更新 减少成本)
===================================================
用 区间DP搭配滑窗概念找字串拼接
用 区间DP切木头 with 最小成本
用 区间DP射气球 with 最大得分
用 区间DP玩捡石头游戏 (minMax)
用 区间DP玩扑克牌游戏 (minMax)
用 区间DP计算回文字串/子序列 (若头尾match，往内继续找 递回)
<-> 反过来就是Central expansion
用 区间DP解最佳股票买卖 (Stock state, Cash state互相流动)
用 区间DP解 House Robbery
<-> Delete and Earn reduce 到这一题 ( 关键步骤:整数i 和 i-1 不可以同时选)
相当于:索引i 和 i-1不可以同时选
用 区间DP解最小旅游成本
用 区间DP生成配对括号 (jacket pattern, pair pattern)
用 格子点DP计算路径树木 (怎么走过来的pattern)
用 格子点DP计算共同子序列 (怎么match，通常会从最后一个或者第一个char开始比较)
===================================================
用DFS+backtracking 玩 Sudoku
用DFS+backtracking 解 N-Queens
===================================================
异曲同工花栗鼠
可爱 >///<