Copy of C++語法

Copy of python語法與加速

Copy of 基礎排序/搜尋

Copy of 1~20

Copy of 20~40

Copy of 40~60

Copy of Hard

待

1. binary index tree
2. trie
   • 各節點為char，路線串到leaf為一個字

算法選擇

1. DP vs Stack
   • 如果只是要記憶上一個狀態，用stack就可以了
   • DP通常是用來連接歷史紀錄
     • 比方說longest valid parenthesis（）（（） 這時如果再加上）就連接到dp[2]的狀態
       • 由()一直延伸判斷過來 ⇒ +( ⇒ +( ⇒ +) ⇒ +) 的狀態
     • 或是regular expression "mis*.*pi" 連接到 *.*的True
       • 由前面一直判斷過來
2. DFS vs BFS
   • DFS 用 recursive 實現(呼叫recursive func其實就是用stack)
   • BFS 用 loop + queue
3. DP vs DFS
   • 把問題視為子問題的疊加、延伸
   • 可以把DFS recursive( ,memo)記憶的部分轉成dp[]
   • 用來解決 search 過程中 重複子問題的情況
   • = Bottom up DFS 解決從後面獨立看會有重複子問題的情況

DP

1. All the variables can be determined by the information from previous state, and also information from the current state. So it can be regarded as a DP solution.
2. DP通常長度都會是n + 1，會預設dp[0] = 0 來代表空字串
3. 定義DP狀態
   • 通常dp[n]都是代表到n-1狀態時（比方說到字串[:n]）的結果值
     • 但也不一定，有時候會設定某些情況下dp[n] 會等於 0，比方說求最大結果值時
     • 這時候請找max(dp)即可獲得目標值