前言

        今天我们学习另一种DP——区间DP。

程序设计思路

        （由于无法从概念上描述题意，这里直接放题目~）

        题意很好理解，要求我们求出合并所有石堆的最小代价。

        首先思考一维DP式，很容易想到将dp[i]定义为合并从第一堆石子到第i堆石子所花费的代价。但是，状态转移方程怎么办？！由于本题中合并的顺序不唯一，第一堆石子也有可能最后合并，所以这个方法不可行。

        这个时候我们需要思考一下：某个区间的最小代价一定是这个区间分为2个区间后这两个区间的代价之和。这样我们可以得到二维DP的定义：dp[i][j]代表从第i堆到第j堆石子合并所需要的最小代价。然后再思考，不难得到：我们可以对某个区间进行分割，这个分割点就是我们要去找的。故我们可以列出以下方程：dp[i][j]=min(dp[i][j],dp[i][i+k]+dp[i+k+1][j]+s[j]-s[i-1]（s[i]为从第一堆石子到第i堆石子代价的前缀和，用来累加代价，自行理解，另外需要预处理）。最后一个问题：dp[i][j]如何初始化？首先如果只有一堆那合并的代价为0，故dp[i][i]=0，而由于我们求最小代价，dp[i][j](i!=j)可以初始化成一个很大的数，方便比较操作。

代码实现

#include <stdio.h>

#include <memory.h>

//今天想重温一下C语言，故用C语言

int n,m[1001],dp[1001][1001],s[1001];//均如题意或已讲解

int min(int a,int b){//C语言没有min函数，所以手搓一个

	if(a<b) return a;

	else return b;

}

main(){

	scanf("%d",&n);

	memset(s,0,sizeof(s));

	memset(dp,0x3f3f3f3f,sizeof(dp));//初始化为大数

	for(int i=1;i<=n;i++) dp[i][i]=0;

	for(int i=1;i<=n;i++) scanf("%d",&m[i]);

	for(int i=1;i<=n;i++) s[i]=m[i]+s[i-1];//计算前缀和

	for(int len=1;len<=n;len++) for(int i=1;i<=n;i++){//len为长度，先计算长度为1的区间之后逐渐累加并重叠

		int j=i+len-1;

		if(j>n) break;//防越界

		for(int k=0;k<len;k++) dp[i][j]=min(dp[i][j],dp[i][i+k]+dp[i+k+1][j]+s[j]-s[i-1]);//dp式

	}

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

	return 0;

}

        可以看到，区间DP的代码很简洁，所以重在理解~

结语

        区间DP没有变式，其O(n³)的时间复杂度也无法进行优化，理解即可。我是faryou，再见！

本文链接：https://blog.faryou.eu.org/post/111.html 转载需经作者授权！