動態規劃法(Dynamic programming)是分治法的變化，將問題細分成一群較簡單的子問題，並以特定順序進行處理進而完成解决。其中一次只解決一個小的子問題，並保存結果供之後使用，避免不必要的重複運算。然後依問題大小漸增順序持續解決所有子問題，將這些小的子問題的結果組成原問題的解法。在許多情況中，如此的運算解法可經證實為已解問題的最佳解法。

動態規劃法時常用於優化的問題處理，其中目的是讓特定的運算達成最大或最小的效果。

基本思路

動態規劃背後的基本思路與分治法非常相似也非常的簡單。大致上，若要解一個給定問題，我們需要了解其不同的部分(即子問題)，按順序求解子問題，前一子問題的解，為後一子問題的求解提供了有用的資訊。在求解任一子問題時，列出各種可能的區域性解，通過決策保留那些有可能達到最優的區域性解，丟棄其他區域性解。依次解決各子問題，最後一個子問題就是初始問題的解。

為了減少計算，會將不同階段存放在二維陣列中。

與分治法的不同

適合於用動態規劃法的問題，經分解後得到的子問題往往不是互相獨立的（即下一個子問題的求解是建立在上一個子問題的解的基礎上，進行進一步的求解）。

適用的情況

能用動態規劃法解決的問題通常有以下幾個特質

1. 最佳子結構原理 如果問題的最佳解所包含的子問題的解也是最佳的，我們就稱該問題具有最佳子結構性質（即滿足最佳化原理）。

2. 無後效性 即子問題的解一旦確定，就不再改變，不受在這之後、包含它的更大的問題的求解決策影響。也就是子問題以後的過程不會影響以前的狀態，只與當前狀態有關。

3. 有子問題重疊性質 在用遞迴演算法自頂向下對問題進行求解時，每次產生的子問題並不總是新問題，有些子問題會被重複計算多次。動態規劃演算法正是利用了這種子問題的重疊性質，對每一個子問題只計算一次，然後將其計算結果儲存在一個表格中，當再次需要計算已經計算過的子問題時，只是在表格中簡單地檢視一下結果，從而獲得較高的效率，降低了時間複雜度。

解題步驟

定義主問題與子問題之間的關係 → 使用陣列儲存子問題的解 → 是否需要找出最佳解路徑