2.3 Dynamic Programming

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

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

2. 最佳子結構 (Optimal Substructure)

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

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

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

動態規劃的方法:

1. Bottom-Up

2. Top-Down

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