資料結構&演算法筆記
  • Introduction
  • 1. Data Structure
  • 1.1 Stack
  • 1.1.1 Stack: Revert String
  • 1.1.2 Stack: Brackets Matching
  • 1.1.3 Stack: Reverse Polish Notation
  • 1.1.4 Stack: Calculattion for Reverse Polish Notation
  • 1.2 Queue
  • 1.2.1 Priority Queue
  • 1.3 Linked List
  • 1.3.1 Linked List - Reorder Function
  • 1.3.2 Ordered Linked List
  • 1.4 Tree
  • 1.4.1 Binary Search Tree
  • 1.4.2 Heap Tree
  • 1.4.3 Red-Black Tree
  • 1.4.3.1 RB Tree Insertion
  • 1.4.3.2 RB Tree Insertion Implementation
  • 1.4.3.3 RB Tree Delete
  • 1.4.3.4 RB Tree Delete Implementation
  • 1.4.4 B-Tree
  • 2. Algorithm
  • 2.1 Sort
  • 2.1.1 Bubble Sort
  • 2.1.2 Selection Sort
  • 2.1.3 Insertion Sort
  • 2.1.4 Merge Sort
  • 2.1.5 Quick Sort
  • 2.1.6 Merge Sort v.s. Quick Sort
  • 2.2 Search
  • 2.2.1 Binary Search
  • 2.3 Dynamic Programming
  • 2.3.1 Fibonacci Series
  • 2.3.2 Find Longest Common Suffix
  • X. Time Complexity Cheat Sheet
Powered by GitBook
On this page

Was this helpful?

2.3 Dynamic Programming

Previous2.2.1 Binary SearchNext2.3.1 Fibonacci Series

Last updated 5 years ago

Was this helpful?

要確認一個問題是否可以用動態規劃去解, 首先要確認是否有以下兩點特性:

  1. 重疊子問題 (Overlapping Sub-problems)

  2. 最佳子結構 (Optimal Substructure)

重疊子問題: 即出現需要重複解同樣的子問題的情境. 在遞迴中, 我們每次都要去重解這些子問題, 不過在動態規劃中, 我們只需要去解一次並且將各個子問題的解儲存起來以供將來使用即可. 比較明顯的案例大概就是Fibonacci數列了.

最佳子結構: 如果一個問題可以用與子問題相同的解法來解的話, 我們稱此問題具有最佳子結構的特性.

綜合上述兩點, 可知Fibonacci數列是可以透過動態規劃來求解的.

動態規劃的方法:

  1. Bottom-Up

  2. Top-Down

Bottom-Up: 假設要解的問題之輸入為N, 那麼就從最小的可能輸入開始解並且儲存其結果, 這樣之後要求比較大的解的時候就可以用之前儲存的結果來求值.