动态规划

一、几个要点

　　1、主体思想：同一件事件不做第二次；

　　2、状态表示：用问题的某些特征参数描述当前的问题；

　　3、状态转移方程：

　　　　状态值之间的递推关系（计算关系）

　　　　　　边界条件　　递推顺序

　　4、实现方式

　　　　自顶向下：记忆化的搜索形式。

　　　　自底向上：递推形式。

二、可以使用动态规划的题目特点：

　　1、一个大问题可以划分为若干子问题

　　　　最优子结构

　　　　子问题：性质一样，但是规模变小的问题。

　　2、在计算时子问题有重叠

　　　　重叠子结构

例1 、hdu2084 数塔问题

1、递归：F（x，y）=max{F（x+1，y），F（x+1，y+1）}+A[x，y]；------超时

2、自下而上记忆化思想（动态规划思想）保证每一个状态最多处理一次。

//基础的DP数塔问题 #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define maxn 103using namespace std;int num[maxn][maxn],n,dp[maxn][maxn];/*int f(int x,int y)    注释部分为递归超时代码 {        if(x==n)        return num[x][y];    else        //注意这里不是num[x+1][y]和num[x+1][y+1]而是函数的递归调用。     {        //return max(f(x+1,y),f(x+1,y+1))+num[x][y];//递归,保存每一层的结果，其实遍历了整个数塔;         res[x]=f(x,y);     }}*/int main(){    int t,i,j,ans;    cin >> t ;    while(t--)    {        ans=0;        cin >> n;        for(i=1;i<=n;i++)            for(j=1;j<=i;j++)                cin >> num[i][j];        memset(dp,0,sizeof(dp));    //初始化        for(i=1;i<=n;i++)            dp[n][i]=num[n][i];        //数塔最后一层赋值给dp的最后一层---后面数组就不会越界。         for(i=n-1;i>=1;i--)            //[1-n]的数塔，从数塔的倒数第二层开始         {            for(j=1;j<=i;j++)        //每层数塔             {                        //状态转移方程                 dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+num[i][j];//将下一层的数中可走路径(两两之间选较大的) 加到这一层             }                        //记录了每一层选择的路径结果          }        cout << dp[1][1] << endl;        //ans=f(0,0);        //cout << ans << endl;     }    return 0;}
        
       
      
     

 　hdu1176 免费陷阱  http://acm.hdu.edu.cn/showproblem.php?pid=1176

 

/*基础dp,免费掉馅饼*/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define maxn 100005    //因为0< T < 100 000  using namespace std;int dp[maxn][13];int main(){    int n,i,j,s,t,m;    while(cin >> n,n)    {        m=0;        for(i=1;i<=n;i++)        {            cin >> s >> t;            if(m
         
          =0;i--)        //从倒数第二层开始,是m层，不是n,n只是输入组数         {            for(j=0;j<11;j++)            {                    //每一层记录从下一层走上来的最优结果                  //这里的j-1其实数组越界了，但是hdu没有报错，还AC了！喵喵喵？？？                dp[i][j]+=max(max(dp[i+1][j-1],dp[i+1][j]),dp[i+1][j+1]);            }                    //状态转移方程         }         cout << dp[0][5] << endl;    //每一层的最优结果到初始位置最优得answer         memset(dp,0,sizeof(dp));    }    return 0; }
         
        
       
      
     

 

 PS：上述数组越界AC了，经多方讨论，以及自爆（= =），事实证明DEV并没有报RE，CB也没有，而且越界访问的值，有的编译器是你定义的其他变量的值，也就是说越界可能会导致你其他变量的值改变（interesting），大概是分配内存时，分配的相邻了吧，但有些编译器是访问的是0 ；越界过多就会爆。

例2、最长上升子序列

1、状态定义：F[ i ]表示序列A[1……i ]的一个最长递增序列的长度（以A[ i ]结尾）；

　状态转移：F[ i ] =max{F[ j ] + 1}　　j<i　　A[ j ] < A[ i ]

　　hdu1257最少导弹拦截系统  http://acm.hdu.edu.cn/showproblem.php?pid=1257

 

/*最长上升子序列LIS*/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define maxn 100005using namespace std;int dp[maxn],num[maxn];//dp[i]定义为以ai为结尾的最长上升子序列的长度int main(){    int n,i,j,ans;    //freopen("Atext.in","r",stdin);    while(cin >> n)    {        ans=0;        for(i=0;i
          
           > num[i]; dp[i]=1;//每一个以ai为结尾的LIS只有两种情况，一种是他自身 } //另一种是它前面比它小的数的LIS加上ai for(i=0;i
          
         
        
       
      
     

例3、最长公共子序列

1、状态定义：F[ i,j ]表示序列A[ 1……i ]与B[ 1……j ]的最长公共子序列长度；

　　状态转移：计算F[ i , j ]时

　　　　若A[ i ] =B[ j ] 　　F[ i , j ]=F[ i-1, j-1] +1;

　　　　   A[ i ] != B[ j ]　　F[ i ,j ]=max{F [ i-1，j ] ，F[ i ，j -1]}

 

例4、背包九讲

　　01背包，多重背包，完全背包……