今天依然手動 redirect 【Day 5】邏輯時間與廣播
反正網路上講 dp 的多的是，dp寫得比我好得多的是～

初學者最大的敵人？

個人情感上，其實是很喜歡 DP 的，
我覺得 DP 是一個「解決好多原來好像無從下手的問題」的思路。
還記得第一次接觸 DP，
好像是演算法課上的背包問題吧，
我就覺得這好實用啊，怎麼有人那麼聰明！

時至今日，幾個月前開始寫 Leetcode，
再次碰到 dp 是 97. Interleaving String，
那時我對於 dp 的印象幾乎是 0 了ＸＤ
感謝當時的朋友非常耐心的劃出了二維表格，
並一步一步解釋給我聽，
最後好不容易聽懂了，又因為 coding 技能還沒上來，
對於 matrix 的操作不熟，因此花了兩小時才寫出來..

最近讀書會的朋友也提了一題 518. Coin Change 2，
說他努力看懂了，卻想不出怎麼建構這樣的思路。
這題算是背包問題的變化題，
而身為資管系的他連背包問題都沒有學過，
難以 get 到我想也是情有可原～

對於很多 dp 初學者來說，
第一步是要先發現這件事情可能可以用 DP 做，
第二步是如何定義 dp 陣列，以及前一項和後一項的轉換式，
第三步則是優化空間複雜度。

而 dp 問題我現在也沒有很熟練，
太千變萬化了，只能多做累積經驗。
而或許對於初學者來說，
最重要的不是練好 dp，而是先將其他基礎資料結構和更常用的演算法學好學扎實。
如果是 new grad，我目前還沒碰到現場考 dp 的公司，頂多是前測。

DP 與其他演算法

DP 主要有兩個性質：

• Optimal Substructure
  如果可以根據子問題的最優解構造最優解，
  則稱該問題具有最優子結構

Greedy 演算法也有 Optimal Substructure，
目的是利用局部最佳解來獲得全域最佳解，
而這樣的做法常常需要數學證明。

• Overlapping Sub-Problems
  如果沒有重複的問題，就沒有記起來的必要，
  因此就會採用 Divide and Conquer。
  例如 merge sort, quicksort

DP 問題的技巧

首先要把問題用數學表達，
看看有哪些參數？
透過這些參數思考，該怎麼樣去分解子問題，該怎麼樣寫出關係式？
DP 通常有兩種形式：

1. Bottom up
2. Top down + 遞迴（memoization）
   通常我寫 dp 都是 bottom up，一步一步建立上去。
   top down + 遞回比較不是我認知的 dp，
   我會歸類為 memoization。