一、动态规划的基本思想
动态规划：适用于子问题不是独立的情况，也就是各子问题包含公共的子子问题，鉴于会重复的求解各子问题，DP对每个问题只求解一遍，将其保存在一张表中，从而避免重复计算。
注意 ：用动态规划解决问题，主要是要找到状态转移方程；
二、动态规划的基本步骤：
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值（最大值或最小值）的那个解。
动态规划算法的设计可以分为四个步骤：
①.描述最优解的结构。
②.递归定义最优解的值。
③.按自底而上的方式计算最优解的值。
④.由计算出的结果创造一个最优解。
三、动态规划问题的特征：
动态规划算法的有效性依赖于问题本身所具有的两个重要性质：
1、最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。
2、重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。
有名的数塔问题：http://acm.hdu.edu.cn/showproblem.php?pid=2084
我们知道，在求解的过程中，很多元素的值都算了不止一次，所有我们可以开个数组把这些已经计算出来的中间值保存下来。
这就是编程的又一大原则:以空间换时间。
我们把原来的数塔保存入一个二维数组g[n][n]里
状态转移方程是:
f[i][j] = g[i][j] + max(f[i+1][j], f[i+1][j+1]) (i < n)
f[i][j] = g[i][j] (i = n)
最后我们输出f[0][0]就可以了。
代码如下：
View Code
1 #include <stdio.h>
2 #include <string.h>
3 #define max(a,b) (a)>(b)?(a):(b)
4 int pre[120][120] , num[120][120] , n ;
5 int dp(int i,int j)
6 {
7 if( pre[i][j] == -1 )
8 pre[i][j] = i == n - 1 ? num[i][j] : max( num[i][j] + dp( i +1 , j ), num[i][j]+ dp ( i + 1 ,j + 1 ) ) ;
9 return pre[i][j];
10 }
11
12 int main(void)
13 {
14 int c , i , j;
15 scanf("%d", &c);
16 while ( c -- )
17 {
18 memset( pre , -1 , sizeof( pre ) ) ;
19 scanf("%d",&n);
20 for(i = 0 ; i < n ; i ++ )
21 {
22 for( j = 0 ; j <= i ; j ++ )
23 scanf( "%d" , &num[i][j] ) ;
24 }
25 printf( "%d\n" , dp( 0 , 0 ) ) ;
26 }
27 return 0;
28 }
总结：
如果各个子问题不是独立的（与分治的不同之处），不同的子问题的个数只是多项式量级，如果我们能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。由此而来的基本思路是，用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。
----------------------------------------------------华丽的分割线---------------------------------------------------------------
参考资料《算法导论》；