石子归并(区间dp)

77 阅读 0 评论 51 点赞

我是靠谱客的博主彩色猫咪，最近开发中收集的这篇文章主要介绍石子归并(区间dp)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

N堆石子摆成一条线。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的代价。计算将N堆石子合并成一堆的最小代价。

例如： 1 2 3 4，有不少合并方法
1 2 3 4 => 3 3 4(3) => 6 4(9) => 10(19)
1 2 3 4 => 1 5 4(5) => 1 9(14) => 10(24)
1 2 3 4 => 1 2 7(7) => 3 7(10) => 10(20)

括号里面为总代价可以看出，第一种方法的代价最低，现在给出n堆石子的数量，计算最小合并代价。
输入
第1行：N（2 <= N <= 100)
第2 - N + 1：N堆石子的数量（1 <= A[i] <= 10000)
输出
输出最小合并代价
输入样例
4
1
2
3
4
输出样例
19

通过这道题目我学习了区间dp，真是是要脑袋爆炸，好在还是有收获的。
希望看博客的时候大家都充满耐心，这一点真的很重要。
dp[i][j]表示从i堆到j堆的最优解
sum[i]表示从1~i堆的的和(只要知道它的意义就好了，作用会在下面说)
与普通dp不一样，区间dp的遍历方式是这样在这里插入图片描述
dp[1][2],dp[2][3],dp[3][4],
dp[1][3],dp[2][4]
dp[1][4],
大家对照着程序，此时就应该明白了l,i,j的作用了，
还有一个k，那么k的作用又是什么呢？
我们来举一个例子，
来求dp[1][3]的值
这个会有两种情况，
1、1和23，2+3 = 5，5+1 = 6，5+6 = 11最终的结果为11
2、12和3，1+2 = 3，3+3 = 6，3+6 = 9最终的结果为9
此时的k就相当于一个分割点，将123分成12、3或者1、23。
上面那个例子不知道大家有没有发现一个特点，加粗的那两个式子，都有一个6，而这个6就是sum[j]-sum[i-1],大家可以自行举例子，表示i到j堆的和

dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
dp[i][k]+dp[k+1][j]这个则表示i-k和k+1-j可以合并的和，好像有点难理解。
这个也应该可以作为模板

#include <stdio.h>
#include <algorithm>
using namespace std;
int dp[1005][1005];
int sum[1005];
int n;
int main()
{
	scanf("%d",&n);
	for(int i = 1;i <= n;i++){
		int x;
		scanf("%d",&x);
		sum[i] += sum[i-1]+x;
	}
	
	for(int l = 1;l < n;l++){
		for(int i = 1,j = l+1;i <= n && j<= n;i++,j++){
			dp[i][j] = 100000;
		//	printf("%d %dn",i,j);
			for(int k = i;k <= j-1;k++){
				dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
			}
		}
	//	printf("n");
	}
	
	printf("%d",dp[1][n]);
	return 0;
}