動態規劃演算法的要素

① 演算法設計的5種基本方法

步驟/方式1
一、【分治法】
分治策略是：對於一個規模為n的問題，若該問題可以容易地解決（比如說規模n較小）則直接解決，否則將其分解為k個規模較小的子問題，這些子問題互相獨立且與原問題形式相同，遞歸地解這些子問題，然後將各子問題的解合並得到原問題的解。
步驟/方式2
二、【動態規劃法】
最優化原理是動態規劃的基礎，任何一個問題，如果失去了這個最優化原理的支持，就不可能用動態規劃方法計算。
使用動態規劃求解問題，最重要的就是確定動態規劃三要素：問題的階段，每個階段的狀態以及從前一個階段轉化到後一個階段之間的遞推關系。
步驟/方式3
三、【貪心演算法】所謂貪心演算法是指，在對問題求解時，總是做出在當前看來是最好的選擇。貪心演算法的基本思路如下：
1. 建立數學模型來描述問題。
2.把求解的問題分成若干個子問題。
3.對每一子問題求解，得到子問題的局部最優解。
4.把子問題的解局部最優解合成原來解問題的一個解。
步驟/方式4
四、【回溯法】
回溯法是一種選優搜索法，按選優條件向前搜索，以達到目標。但當探索到某一步時，發現原先選擇並不優或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態的點稱為「回溯點」。
用回溯法解題的一般步驟：
（1）針對所給問題，定義問題的解空間；
（2）確定易於搜索的解空間結構；
（3）以深度優先方式搜索解空間，並在搜索過程中用剪枝函數避免無效搜索。
步驟/方式5
五、【分支限界法】
基本思想 ：分支限界法常以廣度優先或以最小耗費（最大效益）優先的方式搜索問題的解空間樹。
常見的兩種分支限界法：
（1）隊列式(FIFO)分支限界法：按照隊列先進先出（FIFO）原則選取下一個節點為擴展節點。
（2）優先隊列式分支限界法：按照優先隊列中規定的優先順序選取優先順序最高的節點成為當前擴展節點。

② 演算法基礎之動態規劃法

動態規劃法是一種優化方法，用於解決多階段決策問題，通過分解成單階段子問題並利用它們之間的關系求解。它與分治法和貪心法類似，但處理的是子問題重疊和共享子子問題的情況。動態規劃適用於那些滿足特定性質的問題，如子問題之間存在重疊、求解過程可以以先前結果為基礎等。

動態規劃法解決問題的一般步驟包括：定義狀態、確定狀態轉移方程和計算過程。以多段圖問題為例，通過先向後處理求得源點到各個頂點的最短路徑，再通過優化處理存儲多條最短路徑信息。矩陣連乘問題則需找到最小的乘法次數，通過二維數組記錄每個階段的最小乘積次數。最長公共子序列問題則通過二維數組記錄子序列長度，對所有可能的組合進行比較。

動態規劃問題的時間復雜度通常為多項式級別，如多段圖問題為O(E+K)，矩陣連乘問題為O(n^3)，最長公共子序列問題為O(mn)。空間復雜度較高，如多段圖問題和矩陣連乘問題為O(V+E)，最長公共子序列問題和優化處理後為O(n)或O(mn)。動態規劃實質上是一種以空間換取時間的策略，問題模型需根據問題特性定製。

總結來說，動態規劃需要對問題進行深入分析，定義合適的狀態和狀態轉移方程，並注意空間效率的優化。通過理解這些問題的處理方法，可以提高解決復雜問題的能力。感興趣的朋友可以關注公眾號位元組幺零二四，獲取本文的詳細文檔和更多實例。

③ dp演算法是什麼呢

dp演算法就是動態規劃，是運籌學的一個分支，是求解決策過程最優化的過程。

動態規劃方法一般用來求解最優化問題。這類問題可以有很多可行解，每個解都有一個值，我們希望找到具有最優值的解，我們稱這樣的解為問題的一個最優解，而不是最優解，因為可能有多個解都達到最優值。

動態規劃過程介紹：

確定動態規劃三要素，整個求解過程就可以用一個最優決策表來描述，最優決策表是一個二維表，其中行表示決策的階段，列表示問題狀態。

表格需要填寫的數據一般對應此問題的在某個階段某個狀態下的最優值（如最短路徑，最長公共子序列，最大價值等），填表的過程就是根據遞推關系，從1行1列開始，以行或者列優先的順序，依次填寫表格，最後根據整個表格的數據通過簡單的取捨或者運算求得問題的最優解。