對於給定一個問題，可以將其分解成不同子問題，之後對對其不同子問題 進行求解，再合併子問題解以得出原問題的解。
通常情況下，子問題具有一定的相似性，因此，動態規劃試圖僅僅解決每個子問題一次，從而減少計算量：一旦某個給定的子問題的解已經算出，則將其存儲，以便下次需要同一個子問題時直接查表使用。
分治與動態規劃
共同點：二者都要求原問題具有最優子結構，都是將原問題進行分解，分而治之，分解成若干個子問題，然後將子問題的解進行合併，形成原問題的解。
不同點：
1.找出最優解的性質，刻畫其結構特徵和最優子結構特徵，將原問題分解成若干個子問題；
把原問題分解為若干個子問題，子問題和原問題形式相同或類似，只不過規模變小了。子問題都解決，原問題即解決，子問題的解一旦求出就會被保存，所以每個子問題只需求解一次。
2.遞歸地定義最優值，刻畫原問題解與子問題解間的關係，確定狀態；
在用動態規劃解題時，我們往往將和子問題相關的各個變量的一組取值，稱之為一個「狀態」。一個「狀態」對應於一個或多個子問題， 所謂某個「狀態」下的「值」，就是這個「狀態」所對應的子問題的解。所有「狀態」的集合，構成問題的「狀態空間」。「狀態空間」的大小，與用動態規劃解決問題的時間複雜度直接相關。
3.以自底向上的方式計算出各個子問題、原問題的最優值，並避免子問題的重複計算；
定義出什麼是「狀態」，以及在該「狀態」下的「值」後，就要找出不同的狀態之間如何遷移――即如何從一個或多個「值」已知的 「狀態」，求出另一個「狀態」的「值」(遞推型)。
4.根據計算最優值時得到的信息，構造最優解，確定轉移方程;
狀態的遷移可以用遞推公式表示，此遞推公式也可被稱作「狀態轉移方程」。
有 N 件物品和一個容量為 V 的背包。第i件物品的費用是 c[i]，價值是 w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。
f[i][v] 表示前 i 件物品恰放入一個容量為 v 的背包可以獲得的最大價值。則其狀態轉移方程便是：
將"前 i 件物品放入容量為 v 的背包中"這個子問題，若只考慮第 i 件物品的策略（放或不放），那麼就可以轉化為一個只牽扯前 i-1 件物品的問題。如果不放第 i 件物品，那麼問題就轉化為"前 i-1 件物品放入容量為 v 的背包中"；如果放第 i 件物品，那麼問題就轉化為"前 i-1 件物品放入剩下的容量為 v-c[i] 的背包中」，此時能獲得的最大價值就是 f [i-1][v-c[i]] 再加上通過放入第 i 件物品獲得的價值 w[i] 。
void package(){ for(int i = 1; i <= N; i++) { for(int j = 1; j <= M; j++) { if(j >= weight[i]) { V[i][j] = max(V[i - 1][j], V[i - 1][j - weight[i]] + value[i]); } else { V[i][j] = V[i - 1][j]; } } }}二位數組的空間複雜度顯而易見為 O(nm) ，n 可能不大，但是實際應用的 w 可能會很大，這樣造成了比較大的空間佔用。而仔細觀察發現，矩陣中的值只與當前值的左上角的矩陣裡的值有關。並且是按行進行更新的，所以可以用一個一維數據就能進行狀態的更替，不過要注意更新的方向。
所以依賴關係為：下面依賴上面，右邊依賴左邊；
如果正常地從左到右邊，那麼右邊面等待更新的值需要的依賴（左邊）就會被覆蓋掉，所以應該每行從右邊開始更新。代碼如下：
void packageOpt(){ for(int i = 1; i <= N; i++) { for (int j = M; j >= 1; j--) { if (j >= weight[i]) { V[j] = max(V[j], V[j - weight[i]] + value[i]); } } }}給定兩個字符word1和word2，找到將word1和word2匹配的最大字符，所需操作的最小步數。（每個操作計為1步）。
對單詞允許以下3種操作：
a）插入字符
b）刪除字符
c）替換字符
定義兩個字符串之間的編輯距離：從字符串str1到str2的最少的操作次數。首先，編輯距離是不會大於str1.length + str2.length的（可以通過刪除操作把兩個字符串都轉化為空串）。假設求字符A、B的編輯距離，考慮下面幾種情況：
如果A[i] = B[j]，那麼這時候還需要操作嗎？
這個時候的刪除和替換操作只會讓情況變得更壞，而且插入操作不會使情況變得更好，只要計算
如果A[i] != B[j]，怎麼辦呢？需要進行如下操作：
1. 刪除A串的第一個字符，然後計算
2. 刪除B串的第一個字符，然後計算
3. 修改A串的第一個字符為B串的第一個字符，然後計算
4. 修改B串的第一個字符為A串的第一個字符，然後計算
5. 增加B串的第一個字符到A串的第一個字符之前，然後計算
6. 增加A串的第一個字符到B串的第一個字符之前，然後計算
合併之後可以簡化為以下三步：
1. 從
2. 從
3. 從
那麼此時
註：其中
多步決策可如下表示：
int strSimilar(char *strA, char *strB,int n,int m){ int **A = new int *[n+1]; for(int i = 0; i< n + 1; i++) { A[i] = new int[m+1]; } A[0][0] = 0; A[1][0] = 1; A[0][1] = 1; for (int i = 1; i<=m; i++) { A[0][i] = i; } for (int i = 1; i<=n; i++) { A[i][0] = i; } for(int i = 0; i<n; i++) { for(int j= 0; j<m; j++) { if (strA[i] == strB[j]) { A[i+1][j+1] = A[i][j]; } else { A[i+1][j+1] = min(A[i+1][j], A[i][j+1], A[i][j]) + 1; } } } return A[n][m]; }二維數組複雜度為