動態規劃通常用於解決最優化問題，在這類問題中，通過做出一組選擇來達到最優解。在做出每個選擇的同時，通常會生成與原問題形式相同的子問題。當多於一個選擇子集都生成相同的子問題時，動態規劃技術通常就會很有效，其關鍵技術就是對每個這樣的子問題都保存其解，當其重復出現時即可避免重復求解。
鋼條切割問題
Serling公司購買長鋼條，將其切割為短鋼條出售。切割工序本身沒有成本支出。公司管理層希望知道最佳的切割方案。假定我們知道Serling公司出售一段長為i英寸的鋼條的價格為pi(i=1,2,…，單位為美元)。鋼條的長度均為整英寸。圖15-1給出了一個價格表的樣例。
鋼條切割問題是這樣的：給定一段長度為n英寸的鋼條和一個價格表pi(i=1,2,…n)，求切割鋼條方案，使得銷售收益rn最大。注意，如果長度為n英寸的鋼條的價格pn足夠大，最優解可能就是完全不需要切割。
一、問題分析
長度為n英寸的鋼條共有2n-1種不同的切割方案，因為在距離鋼條左端i(i=1,2,…n)英寸處，總是可以選擇切割或不切割。
如果一個最優解將鋼條切割為k段（對某個1,i2...ik的小段得到的最大收益為
對於
其中，pn對應不切割，對於每個i=1,2,…,n-1，首先將鋼條切割為長度為i和n-i的兩段，接著求解這兩段的最優切割收益ri和rn-i(每種方案的最優收益為兩段的最優收益之和)。當完成首次切割後，我們將兩段鋼條看成兩個獨立的鋼條切割問題實例。通過組合兩個相關子問題的最優解，並在所有可能的兩段切割方案中選取組合收益最大者，構成原問題的最優解。
鋼條切割問題還存在一種相似的但更為簡單的遞歸求解方法：將鋼條從左邊切割下長度為i的一段，只對右邊剩下的長度為n-i的一段繼續進行切割，對左邊的一段則不再進行切割。這樣得到的公式為：二、算法實現
1、樸素遞歸算法
自頂向下遞歸實現參考代碼為：
int CutRod(const int *p, int n)
{
if (n == 0)
{
return 0;
}
int q = -1;
for (int i = 1; i <= n; ++i)
{
int tmp = CutRod(p, n - i);
if (q < tmp)
{
q = tmp;
}
}
return q;
}
分析：自頂向下遞歸實現的CutRod效率很差，原因在於CutRod反復地用相同的參數值對自身進行遞歸調用，即它反復求解相同的子問題。它的運行時間為對於長度為n的鋼條CutRod考察了所有2n-1種可能的切割方案。遞歸調用樹共有2n-1個葉結點，每個葉結點對應一種可能的切割方案。
2、動態規劃算法
樸素遞歸算法之所以效率很低，是因為它反復求解相同的子問題。因此，動態規劃方法仔細安排求解順序，對每個子問題只求解一次，並將結果保存下來。如果隨後再次需要此子問題的解，只需查找保存的結果，而不必重新計算。因此，動態規劃方法是付出額外的內存空間來節省計算空間。
動態規劃有兩種等價的實現方法。
（1）帶備忘的自頂向下法
此方法仍按自然的遞歸形式編寫過程，但過程會保存每個子問題的解（通常保存在一個數組或散列表中）。當需要一個子問題的解時，過程首先檢查是否已經保存過此解。如果是，則直接返回保存的值，從而節省了計算時間；否則，按通常方式計算這個子問題。
（2）自底向上法
這種方法一般需要恰當定義子問題“規模”的概念，使得任何子問題的求解都只依賴於“更小的”子問題的求解。因此，我們可以將子問題按照規模順序，由小至大順序進行求解。當求解某個子問題時，它所依賴的那些更小的子問題都已求解完畢，結果已經保存。每個子問題只需求解一次，當我們求解它時，它的所有前提子問題都已求解完成。
說明：兩種方法得到的算法具有相同的漸進運行時間，僅有的差異是在某些特殊情況下，自頂向下方法並未真正遞歸地考察所有可能的子問題。由於沒有頻繁的遞歸函數調用的開銷，自底向上方法的時間復雜度函數通常具有更小的系數。
下面給出動態規劃-帶備忘的自頂向下過程參考代碼：
1 int MemoizedCutRodAux(const int *p, int n, int *r)
2 {
3 if (r[n] >= 0)
4 {
5 return r[n]; //首先檢查所需的值是否存在
6 }
7
8 int q = -1;
9 if (n == 0)
10 {
11 q = 0;
12 }
13 else
14 {
15 for (int i = 1; i <= n; ++i)
16 {
17 int tmp = p[i] + MemoizedCutRodAux(p, n - i, r);
18 if (q < tmp)
19 {
20 q = tmp;
21 }
22 }
23 }
24 r[n] = q;
25
26 return q;
27 }
28
29 int MemoizedCutRod(const int *p, int n)
30 {
31 int *r = new int[n + 1];
32 for (int i = 0; i <= n; ++i)
33 {
34 r[i] = -1;
35 }
36
37 return MemoizedCutRodAux(p, n, r);
38 }
下面給出動態規劃-自底向上過程參考代碼：
int BottomUpCutRod(const int *p, int n)
{
int *r = new int[n + 1];
r[0] = 0;
for (int i = 1; i <= n; ++i)
{
int q = -1;
for (int j = 1; j <= i; ++j)
{
int tmp = p[j] + r[i - j];
q = q > tmp ? q : tmp;
}
r[i] = q;
}
return r[n];
}
說明：自頂向下與自底向上算法具有相同的漸進運行時間最後給出重構解參考代碼：
1 #include <iostream>
2 using namespace std;
3
4 void ExtendedBUCutRod(const int *p, int n, int *r, int *s)
5 {
6 r[0] = 0;
7 for (int i = 1; i <= n; ++i)
8 {
9 int q = -1;
10 for (int j = 1; j <= i; ++j)
11 {
12 int tmp = p[j - 1] + r[i - j];
13 if (q < tmp)
14 {
15 q = tmp;
16 s[i] = j;
17 }
18 }
19 r[i] = q;
20 }
21 }
22
23 //r[]保存長度為i的鋼條最大收益,s[]保存最優解對應的第一段鋼條的切割長度
24 void PrintBUCutRod(const int *p, int n, int *r, int *s)
25 {
26 ExtendedBUCutRod(p, n, r, s);
27 cout << "長度為" << n << "的鋼條最大收益為:" << r[n] << endl;
28
29 cout << "最優方案的鋼條長度分別為:";
30 while (n > 0)
31 {
32 cout << s[n] << " ";
33 n = n - s[n];
34 }
35 cout << endl;
36 }
37
38 //Test
39 int main()
40 {
41 int n;
42 while (cin >> n)
43 {
44 int *p = new int[n];
45 for (int i = 0; i < n; ++i)
46 {
47 cin >> p[i];
48 }
49 int *r = new int[n + 1];
50 int *s = new int[n + 1];
51
52 PrintBUCutRod(p, n, r, s);
53 }
54
55 return 0;
56 }
一個測試案例為：
