動態規劃（Dynamic Programming, 簡稱DP）是一種算法設計技術，主要用於解決最佳化問題。其核心思想是將問題分解為簡單的子問題，將這些子問題的解決方案存儲起來，以便在解決更大的問題時重用，動態規劃適用於具有以下特點的問題：
最最佳化原理。問題的最優解包含最優的子問題解。
無後效性。即某階段的狀態決策僅取決於當前狀態，與之前的狀態無關。
有重疊子問題。即子問題之間不是獨立的，相同的子問題可能會多次出現。
動態規劃的套用非常廣泛，包括工程技術、經濟、工業生產、軍事和自動化控制等領域。在解決諸如背包問題、生產經營問題、資金管理問題、資源分配問題、最短路徑問題和複雜系統可靠性問題等方面取得了顯著效果。動態規劃的實現通常包括以下幾個步驟：
劃分階段。根據問題的時間或空間特徵，將問題分為若幹個階段。
定義狀態。確定每個階段的狀態變數。
狀態轉移方程。定義狀態之間的轉移方程或關係。
求解。從初始狀態開始，逐步轉移到終止狀態，通過選擇最優決策來最小化或最大化性能指標。
動態規劃通過避免重複計算和利用已解決的子問題解決方案來提高算法效率，這種方法特別適用於解決具有大量重複子問題或子問題之間存在依賴關係的問題。