区间DP入门之石子归并问题

119 阅读 0 评论 79 点赞

我是靠谱客的博主称心皮卡丘，这篇文章主要介绍区间DP入门之石子归并问题，现在分享给大家，希望可以做个参考。

题目描述：

有N堆石子排成一排，每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆，每次合并花费的代价为这两堆石子的和，经过N-1次合并后成为一堆。求出总的代价最小值。
输入
有多组测试数据，输入到文件结束。
每组测试数据第一行有一个整数n，表示有n堆石子。
接下来的一行有n（0< n <200）个数，分别表示这n堆石子的数目，用空格隔开
输出
输出总代价的最小值，占单独的一行
样例输入

复制代码

1
2
3
4
5
3
1 2 3
7
13 7 8 16 21 4 18

样例输出

复制代码

题目来自：NYOJ 737

题目分析：

石子合并是经典的区间DP问题。
本题是将相邻两边进行依次合并，求最小的合并值。
dp[i][j]表示以i为起点，j为终点的合并值。
状态转移方程就是遍历寻找i与j之间一点，进行更新。

复制代码

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

其中sum数组的值就是从i到j所有石子值之和。
开始的时候我以为dp[i][i]应该是该堆石子的值，后面发现这是不对的，应该是0，因为这一堆没有办法合并，所以最小的合并值就是0.

代码如下：

复制代码

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
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
const int MAXN =210;
const int INF =0x3f3f3f3f;

int a[MAXN];
int dp[MAXN][MAXN];//dp[i][j]表示从i取到j的最小值
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        int sum[MAXN][MAXN];//sum[i][j]表示i石子到j石子的值
        for(int i=1; i<=n; i++)
            scanf("%d",&a[i]);
        for(int i=1; i<=n; i++)
        {
            dp[i][i]=0;
            sum[i][i]=a[i];
            for(int j=i+1; j<=n; j++)
               sum[i][j]=sum[i][j-1]+a[j];
        }
        for(int len=2; len<=n; len++)//区间长度
        {
            for(int i=1; i<=n-len+1; i++)//区间起点
            {
                int j=i+len-1;//区间终点
                dp[i][j]=INF;
                for(int k=i; k<j; k++)//寻找区间中间的点来更新dp值
                {
                    dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[i][j]);
                }
            }
        }
        printf("%dn",dp[1][n]);
    }
    return 0;
}