動機

遞迴

貫穿演算法的重點觀念

比起說遞迴是自己call自己，遞迴其實是

  • 分解問題
  • 針對各個case處理，而每個case都是這個遞迴可以處理的

所以寫遞迴，不是去trace (這是最後的手段)

是思考有什麼case，之後相信下一個遞迴可以把問題處理掉 之後針對各個case處理，最後生出需要的資料 千萬不要跳進這個函數里面企圖探究更多細節

遞迴出現在各處，iteration就是recursion的特例。 同時經典演算法的重點也都是在什麼地方有遞迴，像

  • tarjan的求ap或是scc的earliset，就是遞迴，從dfs延伸出去，再補back edge的訊息
  • kmp的fail function，就是一直往前看前面fail的有沒有與現在的字一樣的位置

bottom-up & top-down

遞迴有兩個方向: bottom-up & top-down 也對應到演算法處理問題的方式: 建構 & 分解(再組合) 用方向來看就是 上往下(從頭) & 下往上(從尾)

如樹形DP可以考慮兩種DP順序，一種是從根到葉子，一種是從葉子到根。

像是建tree，可以像segment tree從range去二分，或是像huffman tree把leaf一個一個合成node

遞迴的種類

  • 線性: List = Nil | Cons N List
  • 樹狀: Tree = Nil | Node N Tree Tree
  • 倍增: f(n) = f(f(i))
  • state: f(state1, ...) = f(state2, ...)
  • 其他: 像河內塔 (這個反而不常用到，但不知道為什麼課本總是介紹這個)

模擬

就是照著做，但可以很簡單但也可以很痛苦

  • 先寫好要實現的流程
  • 把每個部分模塊化，寫成函數、結構體或類。
  • 對於一些可能重複用到的概念，可以統一轉化，方便處理
    • “YY-MM-DD 時：分” 把它抽取到一個函數，處理成秒，會減少概念混淆。
    • 求面積時可以存邊長，需要面積時可以用算的

搜尋 與 圖論

兩個很像但關注目標截然不同

搜尋: 重點是 目標 與 減少到目標的距離

圖論: 重點是圖的性質

把兩個接起來的關鍵是狀態，也就是我現在看到哪了 搜尋時的狀態，對應到圖論的點

所以搜尋會有 剪枝與heuristic，因為就算可以看成圖，但是不同狀態變化，所生出的圖不一樣，所以重點是怎麼生圖與如何讓圖生的快一點，或是讓生出的圖變小

圖論就是關注圖的性質，只要能用圖描述(建模)，就能從圖論的工具箱拿出許多工具，像 最短路徑、MST、network flow、SCC、CC 等

列舉 (搜尋)

給出解空間

  • 有那些成分?
  • 可能的情況是什麼？

減少枚舉的空間

  • 枚舉的範圍是什麼？
  • 是所有的內容都需要枚舉嗎？
    • 有時可以透過讓列舉的維度減少
      • a+b=0可以列a，之後就是看-a有沒有被看過

選擇合適的枚舉順序 如果是list，可以是

  • 尾到頭
  • 頭到尾

如果是數字，可以是

  • 大到小
  • 小到大 等等

倍增

倍增思維

分塊

分塊思想

單調

在確認一個函數是否滿足單調性之前，要先能對定義域內的元素比大小，但函數的定義域並不必要是實數

也可以說成，知道要 取 或是 捨棄 那一段區間

單調性: 單調性指的是: 存在一個數字xx 使所有小於xx的數字都不符合條件，不小於xx的數字都符合條件。

一個最有名的例子是binary search，另一個是two pointers

二分搜尋與two pointer binary-search最佳實踐

單調性與順序關係

好用的資源

演算法筆記 cp algorithm oi-wiki 建中校內培訓講義 建中校內培訓簡報