动态规划思想

一、动态规划的基本思想

　动态规划：适用于子问题不是独立的情况，也就是各子问题包含公共的子问题，鉴于会重复的求解各子问题，DP对每个问题只求解一遍，将其保存在一张表中，从而避免重复计算。

注意 ：用动态规划解决问题，主要是要找到状态转移方程；

二、动态规划的基本步骤：

　　动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值（最大值或最小值）的那个解。

动态规划算法的设计可以分为四个步骤：
①.描述最优解的结构。
②.递归定义最优解的值。
③.按自底而上的方式计算最优解的值。
④.由计算出的结果创造一个最优解。

三、动态规划问题的特征：
动态规划算法的有效性依赖于问题本身所具有的两个重要性质：
1、最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。
2、重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解

有名的数塔问题：http://acm.hdu.edu.cn/showproblem.php?pid=2084

我们知道，在求解的过程中，很多元素的值都算了不止一次，所有我们可以开个数组把这些已经计算出来的中间值保存下来。
　　这就是编程的又一大原则:以空间换时间。
　　我们把原来的数塔保存入一个二维数组num[n][n]里
　　状态转移方程是:
　　dp[i][j] = num[i][j] + max(dp[i+1][j], dp[i+1][j+1]) (i < n)
　　dp[i][j] = dp[i][j] (i = n)
　　最后我们输出dp[0][0]就可以了。

代码：

#include<iostream>
#include<cstdio>
#define N 101
using namespace std;
int num[N][N],dp[N][N];
int n;
int main()
{ int n;
   scanf("%d",&n);
  for(int i=0;i<n;++i)
    for(int j=0;j<=i;++j)
      scanf("%d",&num[i][j]);
      for(int i=n-1;i>=0;--i)
        for(int j=0;j<=i;++j)
         { if(i==n-1) dp[i][j]=num[i][j];
            else  dp[i][j]=num[i][j]+max(dp[i+1][j+1],dp[i+1][j]);
         }
         printf("%d\n",dp[0][0]);
         return 0;
}

总结：

如果各个子问题不是独立的（与分治的不同之处），不同的子问题的个数只是多项式量级，如果我们能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。由此而来的基本思路是，用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。