[溫馨] 編碼花栗鼠
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
===================================================
異曲同工花栗鼠
可愛 >///<
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.37.192.233 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/talk/M.1711810654.A.100.html
→
03/30 23:19,
2月前
, 1F
03/30 23:19, 1F
推
03/31 04:41,
2月前
, 2F
03/31 04:41, 2F