动态规划可求最优解问题，但有条件限制，每一层最优解可知。
递归动态规划
与分治思想有类似之处，但在递归基础上，用一张表存储计算过程中每一层的”最优解“，避免重复计算已经得出的计算结果。
Rod-Cutting Problem
问题描述：
给你一根长n英尺的棒子和一份关于该棒子的价目表如下（其中 i = 1,2,3,…,n），请问如何将这根棒子卖出最高的价格，可以对棒子进行切割。
thinking path:
从i=1 to 10进行枚举尝试，例如，砍1米开始砍，那么剩下的9米就会成为新的”问题“，进行递归。易得递推式：
r(i)=max(p[i]+r(n-i)); n为rod总长
根据递推式，写出递归伪代码:
CUT(p,n)
if n==0 return 0;
for (int i = 1; i <= n; i++)
q = max(q,p[i]+cut(p,n-i));
return q;
结合Dynamic Programming思想：
用一个数组result来存放每一段的结果。
CUT(result,p,n)
if (r[n]>=0) return r[n]
if n==0 return 0
else
q=-∞
for (int i = 1; i <= n; i++)
if (q<p[i]+cut(result,p,n-i))
q=max(p[i]+cut(result,p,n-i))
r[n]=q
return r[n]
完整C++代码如下:
1 #include <iostream> 2 3 4 using namespace std; 5 6 7 //m is the total 8 int cut(int* table, int n, int* r) { 9 if (r[n-1]>=0) return r[n-1]; //r 存放切长度为n时的最优解，避免重复运算直接返回 10 if (n == 0) { 11 return 0; 12 } else { 13 //需要一个当前状态下最优解的临时参数存储 14 int temp = -9999; 15 for (int i = 1; i <= n; i++) { 16 int p_rest = cut(table,n-i,r); 17 if (temp < p_rest + table[i-1]) { 18 temp = p_rest+table[i-1]; 19 } 20 } 21 r[n-1]=temp; 22 return r[n-1]; 23 } 24 } 25 int main() { 26 int table[] = {1,5,8,9,10,17,17,20,24,30}; 27 28 int *result = new int[10]; 29 30 for (int i = 0; i < 10; i++) { 31 result[i] = -1; 32 } 33 34 cout << cut(table,6,result) << endl; 35 36 return 0; 37 }