区间DP

区间DP，在我的初步理解是，在这个区间内部进行DP操作，得到一个最优解，这个区间是可以分割成小的区间，并且由小的区间合并到大的区间

括号匹配

给定一个区间，问子序列中，成对匹配的子序列最长是多少。

首先区间DP应该先写出动态转移方程，

首先应该预处理，假设括号不匹配，那么状态转移

DP[i][j]=DP[i+1][j];

如果S[i]和S[k]成功匹配，我们转移是从两边转移

DP[i][j]=MAX(DP[i][j],DP[i][K-1]+DP[K+1][j]+2);

代码:

#include<iostream>

#include<stdio.h>

#include<string.h>

using namespace std;

char s[103];

int dp[103][103];

int main(){

  while(scanf("%s",s+1) && s[1]!='e'){

    int len=strlen(s+1);

    memset(dp,0,sizeof(dp));

    for (int i=len-1;i>=1;i--)//左边间

        for (int j=i+1;j<=len;j++)//右边界

        {

           dp[i][j]=dp[i+1][j];//z假设他不匹配那么dp[i+1][j]只能由dp[i][j]推出

           for (int k=i+1;k<=j;k++)

           {

               if ((s[i]=='(' && s[k]==')') || (s[i]=='[' && s[k]==']'))//匹配成功

                  dp[i][j] = max(dp[i][j],dp[i+1][k-1]+dp[k+1][j]+2);//转移方程

           }

        }

      printf("%d\n",dp[1][len]);

  }

  return 0;

}

合并石子

给你N堆石子，只能合并相邻的石子，并且花费为两堆石子权值之和，求合成一堆所需费用。

分析：

一般对于这种DP给定区间求最小值，首先应该初始化INF.

我们来分析一下这个DP，这是区间DP最基础的类型，我们首先应该分析这个DP应该是二维的，因为只有一段，所以可以很容易写出DP转移方程

  DP[i][j]代表，在i,j范围内合并所需要的最小权值，而K作为分割，在i->j里面遍历，而SUM[i]][j]为石头的权值，表示合并i->k->j所需要的权值

  Sum[i][j]=Sum[i][k]+Sum[k][j];

  DP[i][j]=max( DP[i][j] , DP[i][k]+DP[k+1][j]+sum[i][j] );

代码：

#include<iostream>

#include<stdio.h>

#include<string.h>

#define INF 0x3f3f3f3f

using namespace std;

int main(){

   int n;

   int dp[205][205];

   int sum[205][205];//石头数量

   int a[205];

   while(~scanf("%d",&n)){

      memset(dp,0,sizeof(dp));

      memset(sum,0,sizeof(sum));

      for(int i=1;i<=n;i++){

         scanf("%d",&a[i]);

         sum[i][i]=a[i];

      }

      for (int i=1;i<=n;i++)

        for (int j=1;j<=n;j++){

         dp[i][j]= i==j? 0 : INF;//初始化操作

      }

      for (int len=1;len<n;len++){//首先枚举每个长度

         for (int i=1;i+len<=n;i++){//再枚举每个初始点

            int j=len+i;//结束点

            for (int k=i;k<j;k++){//分割点

                sum[i][j]=sum[i][k]+sum[k+1][j];

                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[i][j]);

            }

         }

      }

      cout<<dp[1][n]<<endl;

   }

  return 0;

}

总结：区间DP的DP方程其实并不难写

大概就是DP[i][j]=MAX/MIN(DP[i][j],DP[i][k]+DP[k][j]+w);

W代表这样合并的影响