動態規劃通常用來解決最優化問題，通過做出一組選擇來達到最優解。在做出每個選擇的同時，通常會生成與原問題形式相同的子問題。當多于一個選擇子集都生成相同的子問題時，動態規劃技術通常就會很有效，其關鍵技術就是對每個這樣的子問題都保存其解，當其重復出現時即可避免重復求解。
動態規劃（dynamic PRogramming）與分治方法相似，都是通過組合子問題的解來求解原問題。分治方法將問題劃分為互不相交的子問題，遞歸的求解子問題，再將他們的解組合起來，求出原問題的解。與之相反，動態規劃應用于子問題重疊的情況，不同的子問題具有公共的子子問題。在這種情況下，分治算法會做許多不必要的工作，它會反復地求解那些公共子問題，而動態規劃算法對每個子子問題只求解一次，將其解保存在一個表格中，從而無需每次求解一個子子問題時都重新計算，避免了這種 不必要的計算工作。 動態規劃常用來求解最優化問題（optimization problem），這類問題可以有很多可行解，每個解都有一個值，尋找最優值（最大值或最小值）的解，稱這樣的解為問題的一個最優解（an optimal solution），而不是最優解（the optimal solution），因為有可能有多個解都達到最優值。 通常用4個步驟來設計一個動態規劃算法： 1. 刻畫一個最優解的結構特征； 2. 遞歸的定義最優解的值； 3. 計算最優解的值，通常采用自底向上的方法； 4. 利用計算出的信息構造一個最優解 。
鋼條切割問題：給定一段長度為n英寸的鋼條和一個價格表pi（i=1,2，???，n），求切割鋼條方案，使得銷售收益rn最大，鋼條可以0切割。
長度為n英寸的鋼條共有2^（n-1）中不同的切割方案，因為在距離鋼條左端i（i=1,2,???，10）英寸出，我們總是可以選擇切割或不切割。一個最優解就是將鋼條切割為k段（1<=k<=n），那么最優切割方案為 n=i1+i2+???+ik 將鋼條切割為長度分別為i1，i2，???，ik的小段，得到最大收益 rn=pi1+pi2+???+pik 更一般的，對于rn，可以用更短的鋼條的最優切割收益來描述它 rn=max（pn，r1+r(n-1)，r2+r(n-2)，???，r(n-1)+r1）
根據上面得到的式子，采用遞歸的方法，偽代碼如下：
CUT_ROD(p, n)if n == 0 return 0q = -1for i = 1 to n q = max (q, p[i] + CUT_ROD(p, n - i)return q從上面的遞歸中可以看出，每個n值，都會反復的計算前面已經計算過的值，當n比較大時，遞歸調用的工作量會爆炸性的增長，所以應該采用動態規劃的方法求解。
動態規劃有兩種等價的實現方法。 第一種方法稱為帶備忘的自頂向下法（top-down with memorization）。此方法仍按照自然的遞歸形式編寫過程，但過程會保存每個子問題的解（通常保存在一個數組或哈希表中），我們稱這個遞歸過程是帶備忘的（memoized）。 第二種方法稱為自底向上法（bottom-up method）。這種方法一般需要恰當定義子問題“規?！钡母拍睿沟萌魏巫詥柕那蠼舛贾灰蕾囉凇案〉摹弊訂栴}的求解，因而可以將子問題按規模排序，按由小至大的順序進行求解。 兩種方法得到的算法具有相同的漸進運行時間，僅有的差異是在某些特殊情況下，自頂向下方法并未真正遞歸地考察所有可能的子問題，由于沒有頻繁的遞歸函數調用的開銷，自底向上方法的時間復雜性函數通常具有更小的系數。 這里采用第二種方法的偽代碼如下：
BOTTOM_UP_CUT_ROD(p, n)let r[n] be a new arrayr[0] = 0for j = 1 to n q = -1 for i = 1 to j q = max(q, p[i] + r[j – i]) r[j] = qreturn r[n]上面的偽代碼已經計算出最優解的值，但缺少最優解的方案，可以稍加修改，添加數組s記錄n英寸鋼條最優切割方案的第一段切割長度：
EXTENDED-BOTTOM-UP-CUT-ROD(p, n)let r[n] and s[n] be new arraysr[0] = 0for j = 1 to n q = -1 for i = 1 to j if q < p[i] + r[j – i] q = p[i] + r[j – i] s[j] = i r[j] = qreturn r and s通過下面的偽代碼來輸出完整的最優切割方案：
PRINT_CUT_ROD_SOLUTION(p, n)(r, s) = EXTENDED-BOTTOM-UP-CUT-ROD(p, n)while n > 0 print s[n] n = n – s[n]給定n個矩陣的鏈[A1，A2，???，An]，矩陣Ai的規模為p(i-1)*pi（1<=i<=n），求完全括號化方案，使得計算乘積A1A2???An所需標量乘法次數最少。
和鋼條切割問題相似，A1A2???An其實就可以寫成A1???AkA(k+1)???An，其中A1???Ak和A(k+1)???An就成為了兩條子鏈，同理，子鏈亦可往下分解，原來的問題就變成了求解這些子鏈的的問題。
令m[i, j]表示計算矩陣鏈所需標量乘法次數的最小值，原問題的最優解的值為m[1, n]，很容易，我們得到 m[i, j] = m[i, k] + m[k+1, j] + p(i-1)pkpj，當i=j時，m[i , j]=0.
根據上面的遞歸公式，假設矩陣Ai的規模為p(i-1)*pi，它的出入序列是p=[p0，p1，???，pn]，過程中用輔助表m保存代價m[i, j]，用輔助表s記錄最優值m[i, j]對應的分割點k。偽代碼如下：
MATRIX_CHAIN_ORDER(p)n = p.length – 1let m[n+1][n+1] and s[n][n+1] be new tablesfor i = 1 to n m[i, i] = 0 for i =2 to n for i = 1 to n-l+1 j = i + l – 1 m[i , j] = -1 for k = i to j-1 q = m[i, k] + m[k+1, j] + p(i-1)pkpj if m[i, j] < 0 or q < m[i, j] m[i, j] = q s[i, j] = kreturn m and s利用遞歸求解的思路遞歸的輸出最優括號方案，偽代碼如下：
PRINT_OPTIMAL_PARENS(s, i, j)if i == j return “A”ielse print “(“ PRINT_OPTIMAL_PARENS(s, i, s[i, j]) PRINT_OPTIMAL_PARENS(s, s[i, j] + 1, j) print “)”新聞熱點
疑難解答
