6.1 算法解釋

這裡我們引用一下維基百科的描述：「動態規劃（Dynamic Programming, DP）在尋找有許多重疊子問題情況的最優解時非常有效。它將問題重新分解成子問題。為了避免多次解決這些子問題，它們的結果會逐步被計算並保存，從簡單的問題開始，直到整個問題被解決。因此，動態規劃保存遞迴中的結果，從而避免在解決相同問題時浪費時間⋯⋯ 動態規劃只能應用於有最優子結構的問題。最優子結構的意思是，局部最優解能夠決定全局最優解（對某些問題來說這個要求不完全滿足，因此有時需要引入一定的近似）。簡單來說，問題能夠分解成子問題來解決。」

通俗來說，動態規劃與其他遍歷算法（如深度優先搜索或廣度優先搜索）的最大區別在於，動態規劃保存子問題的解，避免重複計算。解決動態規劃問題的關鍵是找到狀態轉移方程，通過計算與保存子問題的解來求解最終問題。

同時，我們也可以對動態規劃進行空間壓縮，以節省空間消耗。這一技巧筆者會在後續題目中介紹。

在某些情況下，動態規劃可以視為帶有狀態記錄（memoization）的優先搜索。狀態記錄的意思是，如果一個子問題在優先搜索時已經計算過一次，可以將結果保存下來，之後再次遍歷到該子問題時可以直接返回保存的結果。動態規劃是自下而上的，先解決子問題再解決父問題；而帶有狀態記錄的優先搜索是自上而下的，從父問題搜索到子問題，如果重複搜索到同一個子問題則記錄其狀態以防重複計算。如果題目需求的是最終狀態，使用動態規劃會比較方便；如果需要輸出所有的路徑，則使用帶有狀態記錄的優先搜索會更適合。