扣筆記 CodeNotes by kaiyuncheng

動態規劃 Dynamic programming

• using ‘Cache’ Memoization

動態規劃的基本思想是將「原始問題」分解成多個「子問題」，先求解並「儲存」這些子問題的解到 cache，然後通過這些子問題的解來提供給原問題。這樣做的目的是避免重複計算，從而提高算法的效率。

• Dynamic Programming = Divide-and-Conquer + Memoization (Cache)
  與 分而治之 Divide-and-Conquer 很像，但最大的差別是子問題大多類似，並先儲存子問題的解到 cache，之後需要使用到時就不用重複計算