区间DP(合并石子)的笔记

?总是从最后一步进行分析：最后一次合并一定是左边连续的一部分和右边连续的一部分进行合并。

f[i][j]表示为从编号i到编号j合并完成为一堆的最小代价。

当i < j时，f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);（因为是最小代价，所以用min函数）

当i == j时，就是只有一堆石子那么，f[i][j] = 0;

石子合并代价计算过程：
左堆的总数量 ： s[k]-s[i-1]
右堆的总数量 ： s[j]-s[k+1-1]
合并左右堆得代价 ： s[k]-s[i-1]+s[j]-s[k+1-1] = s[j]-s[i-1]

由以上过程推导，所以前面的状态转移方程才能直接得到s[j] - s[i - 1]

//区间DP 石子合并
#include<iostream>
using namespace std;
const int N = 310;
int f[N][N], n, s[N];//前缀和

int main() 
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> s[i], s[i] += s[i - 1];

	//长度从2开始枚举，因为长度为1的石堆不需要合并
	for (int len = 2; len <= n; ++len)//枚举长度
	{
		for (int i = 1; i + len - 1 <= n; ++i)//枚举左端点
		{
			int j = i + len - 1;//右端点
			f[i][j] = 1e8;//给一个很大的数就行
			for (int k = i; k < j; ++k)//k要小于j
			{
				f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
			}
		}
	}
	cout << f[1][n];
	return 0;
}

?区间DP的第一层循环一般是枚举长度，然后就是左右端点。上述代码中的s数组是前缀和数组，

k在i到j之间。注意k不能等于j，因为当k等于j，那么k + 1就会大于j，就会导致数组越界。

就是i到k的一堆石子和k + 1到j的一堆石子合并。由于动态规划的最优解通常是自底向上求解的，所以在对f[i][j]赋值的时候，f[i][k]和f[k + 1][j]已经被更新过了。