# 動態規劃 > 原文： [https://www.programiz.com/dsa/dynamic-programming](https://www.programiz.com/dsa/dynamic-programming) #### 在本教程中，您將學習什么是動態規劃。 此外，您還將發現動態規劃和貪婪算法之間的比較，以解決問題。 動態規劃是計算機編程中的一種技術，可幫助有效解決一類具有重疊子問題和[最佳子結構](https://en.wikipedia.org/wiki/Optimal_substructure)屬性的問題。 這些問題涉及重復計算相同子問題的值以找到最佳解決方案。 * * * ## 動態規劃實例 以生成斐波那契數列為例。 如果序列是`F(1)F(2)F(3)........ F(50)`，則遵循規則`F(n) = F(n-1) + F(n-2)`） ``` F(50) = F(49) + F(48) F(49) = F(48) + F(47) F(48) = F(47) + F(46) ... ``` 注意，子問題如何重疊，我們需要計算`F(48)`才能計算`F(50)`和`F(49)`。 這正是動態規劃大放異彩的算法。 * * * ## 動態規劃的工作原理 動態規劃通過存儲子問題的結果來工作，以便在需要它們的解決方案時就可以使用它們，而我們無需重新計算它們。 這種存儲子問題值的技術稱為記憶。 通過將值保存在數組中，我們節省了計算遇到的子問題的時間。 ``` var m = map(0 → 0, 1 → 1) function fib(n) if key n is not in map m m[n] = fib(n ? 1) + fib(n ? 2) return m[n] ``` 通過備注進行動態規劃是一種自頂向下的動態規劃方法。 通過反轉算法的工作方向，即從基本情況開始并朝解決方案努力，我們還可以自下而上地實現動態規劃。 ``` function fib(n) if n = 0 return 0 else var prevFib = 0, currFib = 1 repeat n ? 1 times var newFib = prevFiB+ currFib prevFib = currFib currFib = newFib return currentFib ``` * * * ## 遞歸與動態規劃 動態規劃主要應用于遞歸算法。 這不是巧合，大多數優化問題都需要遞歸，并且將動態規劃用于優化。 但是并非所有使用遞歸的問題都可以使用動態規劃。 除非像斐波那契數列問題那樣存在重疊的子問題，否則遞歸只能使用分治的方法來解決。 這就是為什么諸如歸并排序的遞歸算法不能使用動態規劃的原因，因為子問題不會以任何方式重疊。 * * * ## 貪婪算法與動態規劃 [貪婪算法](https://www.programiz.com/dsa/greedy-algorithm)與動態規劃類似，因為它們都是優化工具。 但是，貪婪算法會尋找局部最優解，或者換句話說，是貪婪的選擇，以期找到全局最優解。 因此，貪婪的算法可能會做出一個猜測，即看起來當時是最優的，但代價很高，并且不能保證全局最優。 另一方面，動態規劃會找到子問題的最佳解決方案，然后做出明智的選擇，以合并那些子問題的結果以找到最佳解決方案。