小北
0%

区间dp

发表于 更新于 分类于

区间dp

概念

区间dp——顾名思义就是区间上的dp，利用小区间上的最优解求出所求区间的最优解。

思路

NOTICE:区间不一定指某个数的左右两个区间，可能以某种形式表示出来。
KEY:如果数据的某段区域最值可以由小区间递归而来，就可以联想区间dp。
形式：一般由长度划分，再去枚举左端点和右端点，状态转移方程由数据之间的运算性质决定。

板子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
memset(dp,0x3f3f3f,sizeof(dp));  //初始化dp数组
for(int i=1;i<=n;i++)
{
    dp[i][i]=0;
    sum[i]=sum[i-1]+a[i];
}
for(int len=2;len<=n;len++)  //区间长度
{
	for(int l=1;l<=n-len+1;l++)   //左端点
	{
		int r=l+len-1;   //右端点
		for(int k=l;k<r;k++)    //分隔点
		{
			dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1]);  //转移方程
		}
	}
}

例题

  • 石子合并2
    • 题意：将n堆石子绕圆形操场排放，现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记做该次合并的得分。
      请编写一个程序，读入堆数n及每堆的石子数，并进行如下计算：
      选择一种合并石子的方案，使得做n-1次合并得分总和最大。
      选择一种合并石子的方案，使得做n-1次合并得分总和最小。
    • 分析：可以看出这可以由小区间的最优解去得到大区间的最优解，所以可以用区间dp来写；
    • 代码： 
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      65
      66
      67
      68
      69
      70
      71
      72
      73
      74
      75
      76
      77
      78
      79
      80
      81
      82
      83
      84
      85
      86
      #include<stdio.h>
      #include<algorithm>
      #include<iostream>
      #include<string.h>
      using namespace std;

      int dp[405][405];
      int a[405];
      int sum[205];
      int n;
      void init_min()
      {
          int i;
          memset(dp,0x3f,sizeof(dp));
          memset(sum,0,sizeof(sum));
          for(i=1;i<=2*n;i++)
          {
              dp[i][i]=0;
              sum[i]=sum[i-1]+a[i];
          }
      }
      void init_max()
      {
          int i;
          memset(dp,0,sizeof(dp));
          memset(sum,0,sizeof(sum));
          for(i=1;i<=2*n;i++)
          {
              dp[i][i]=0;
              sum[i]=sum[i-1]+a[i];
          }
      }
      void cal_min()
      {
          for(int len=2;len<=n;len++)  //区间长度
          {
              for(int l=1;l<=2*n-len+1;l++)   //左端点
              {
                  int r=l+len-1;   //右端点
                  for(int k=l;k<r;k++)    //分隔点
                  {
                      dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1]);  //转移方程
                  }
              }
          } 
          int ans=0x3f3f3f;
          for(int i=1;i<=n;i++)
          {
              ans=min(ans,dp[i][i+n-1]);
          }
          printf("%d\n",ans);
      }
      void cal_max()
      {
          for(int len=2;len<=n;len++)  //区间长度
          {
              for(int l=1;l<=2*n-len+1;l++)   //左端点
              {
                  int r=l+len-1;   //右端点
                  for(int k=l;k<r;k++)    //分隔点
                  {
                      dp[l][r]=max(dp[l][r],dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1]);  //转移方程
                  }
              }
          } 
          int ans=0;
          for(int i=1;i<=n;i++)
          {
              ans=max(ans,dp[i][i+n-1]);
          }
          printf("%d\n",ans);
      }
      int main()
      {
          scanf("%d",&n);
          for(int i=1;i<=n;i++)
          {
              scanf("%d",&a[i]);
              a[i+n]=a[i];
          } 
          init_min();
          cal_min();
          init_max();
          cal_max();
          return 0;
      }

在刚开始写这道题时，当成了是一条直线进行选择，后来才注意到是环，那么我们也可以把数据组成环，把1–n 的数据继续放在n+1到2n的区间数据里，然后以n个为区间长度进行运算。

石子合并1几乎就可以直接用板子套用了。