原题链接：AcWing 282. 石子合并
题意：合并 N 堆石子，每次只能合并相邻的两堆石子，求最小代价
解题思路：
关键点：最后一次合并一定是左边连续的一部分和右边连续的一部分进行合并
状态表示：$f[i][j]$ 表示将 $i$ 到 $j$ 这一段石子合并成一堆的方案的集合，属性 Min
状态计算：
（1） $i < j$ 时，$f[i][j] = \min\limits_{i\leq k \leq {j - 1}}\{f[i][k]+f[k+1][j] + s[j] -s[i - 1]\}$
（2）$i = j$ 时， $f[i][i] = 0$ （合并一堆石子代价为 0）
问题答案： $f[1][n]$
区间 DP 常用模版
所有的区间dp问题枚举时，第一维通常是枚举区间长度，并且一般 len = 1 时用来初始化，枚举从 len = 2 开始；第二维枚举起点 i （右端点 j 自动获得，j = i + len - 1）
模板代码如下：
for (int len = 1; len <= n; len++) { // 区间长度
for (int i = 1; i + len - 1 <= n; i++) { // 枚举起点
int j = i + len - 1; // 区间终点
if (len == 1) {
dp[i][j] = 初始值
continue;
}
for (int k = i; k < j; k++) { // 枚举分割点，构造状态转移方程
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i][j]);
}
}
}
本题C++代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 307;
int a[N], s[N];
int f[N][N];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
s[i] += s[i - 1] + a[i];
}
memset(f, 0x3f, sizeof f);
// 区间 DP 枚举套路：长度+左端点
for (int len = 1; len <= n; len ++) { // len表示[i, j]的元素个数
for (int i = 1; i + len - 1 <= n; i ++) {
int j = i + len - 1; // 自动得到右端点
if (len == 1) {
f[i][j] = 0; // 边界初始化
continue;
}
for (int k = i; k <= j - 1; k ++) { // 必须满足k + 1 <= j
f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
}
}
}
cout << f[1][n] << endl;
return 0;
}
补充1：从下往上倒着枚举状态
除了按长度枚举，也可以倒着枚举，因为只要保证每种状态都被提前计算即可
从下往上倒着枚举，可以保证你算dp[i][j]时，dp[i][k]和dp[k + 1][j]一定是被提前计算好的，而从上往下枚举则无法保证这一点。所以我们采用倒着枚举
图解：
#include <iostream>
using namespace std;
const int N = 307;
int s[N];
int f[N][N];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> s[i];
s[i] += s[i - 1];
}
for (int i = n; i >= 1; i--) {
for (int j = i; j <= n; j++) {
if (j == i) {
f[i][j] = 0;
continue;
}
f[i][j] = 1e9;
for (int k = i; k < j; k++) {
f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
}
}
}
cout << f[1][n] << endl;
return 0;
}
补充2：记忆化搜索
如果学过后面的记忆化搜索，那也可以用下面的代码。虽然时间会比递推稍微慢一丢丢，但是呢他的思路比较好写
#include <iostream>
#include <cstring>
using namespace std;
const int N = 307;
int a[N], s[N];
int f[N][N];
// 记忆化搜索：dp的记忆化递归实现
int dp(int i, int j) {
if (i == j) return 0; // 判断边界
int &v = f[i][j];
if (v != -1) return v;
v = 1e8;
for (int k = i; k <= j - 1; k ++)
v = min(v, dp(i, k) + dp(k + 1, j) + s[j] - s[i - 1]);
return v;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
s[i] += s[i - 1] + a[i];
}
memset(f, -1, sizeof f);
cout << dp(1, n) << endl;
return 0;
}
那个记忆化搜索挺有用的
记忆化搜索好评
大佬，这里我想引用你的模板记到我笔记里复习可以吗？
贴个链接应该没问题
小姐姐，我对状态转移方程s[j]-s[i-1]这个不理解，这个应该怎么理解？感觉状态转移方程好难想啊
f[i[[k]代表合成[i~k]这个区间的最小代价，f[k+1][j]代表合成[k+1,j]区间的最小代价
f[i][k] + f[k+1][j]代表的是合成[i~k]这一堆石子和合成[k+1~j]这一堆石子代价
s[j]-s[i-1]代表的合并[i~k] [k+1~j] 这两堆石子的代价
好的，谢谢。感觉dp状态转移方程太难想了
感觉只有多做累计经验
前缀和的意思
这个是前缀和 就是 j到i所有石子的和
这个解释爱了呀
懂了qaq
假设有4堆石子:1 3 5 2
i=1,k=2,j=4
f[1,2]:将第一堆和第二堆这两堆石子合并成一堆石子
f[3,4]:将第三堆和第四堆这两堆石子合并成一堆石子
所以经过f[1,2]+f[3,4]后我们就成功将1 3 5 2这四堆石子合并成了4 7 这两堆石子
不过别忘了题目要求的是将这四堆石子合并成一堆石子
所以我们还需将4 7 这两堆石子合并成一堆石子
因此还需付出4+7=11的代价；而11=[1,4]的前缀和
总代价:(1+3)+(5+2)+4+7=22
6
6
啊？原来是这样理解啊.....
www但是那既然这样，合并[k+1,j]区间的最小代价为什么不能也用s[j]-s[k]来表示呢，而是要用f[k+1][j]
个人理解是 这里的 s[j] - s[i - 1]合并的是 最终[i, k]和[k + 1, j]这两堆大石子
而您说的 [k + 1, j]这个区间则是在某次循环中成为新的’ i ‘和’ j ‘ 再次合并
是一个递归的过程 不知道对不对
6666，我终于懂了。
终于懂了，感谢大佬!!!
谢谢，我悟了！
f[ i ][ k] + f[ k + 1 ][ j ] 并不能表示当前两堆石子的合并，而是s[ j ] - s[ i - 1 ]
为什么在枚举左端点的时候限制条件可以是i+len-1呢？就是这个非常不明白
你好，限制条件是右端点j<=n，而j等于i+len-1
哦，那么k可以从i+1开始吗，这样就保证了左半区间的长度一定是大于0的
我试了一下，答案有点问题。。。
这里区间长度指的是点的个数，比如[i, i]的区间长度是1，[i, i + 1]的区间长度是2，所以k要从i开始
哦，懂了懂了，另外怎么判断一个题是需要用dp写法呢？
就是区间dp
这个靠经验吧，其实我会的也不多，感觉就是如果你分析题目发现要表示 一段区间[i,j]的某个量，那就可以考虑用区间dp，如果是从[1,i]的某个量，那么一般是正常的dp，比如背包问题那种类型。
嗯嗯好的，知道了，多谢
赞
因为区间长度为len=j-i+1,所以j=len+i-1
一样的，我们只要能保证在求某个状态时它的子状态都已经求过就行了，例如：这段代码在求dp[j][i] 时，dp[j][k] 和dp[k+1][i] 一定是已经求过的。
感觉写的不如费解的开关题解的陈英一根
为什么我觉得这个不对呢 ？正序的时候f[k + 1][j]不是默认是0吗？为什么会得到正确答案，求大佬解惑
f数组记录的是在本次合并之前的代价之和，而s[j]-s[i-1]为本次合并的代价
记忆化搜索的方式可以使用一个二维数组来表示中间状态的计算结果。下面是一个示例图示：
假设输入的数列为 [3, 1, 2, 4, 3]，我们使用记忆化搜索的方式计算将整个数列分成若干个连续的非空子段所需的最小和。
首先，我们定义一个二维数组f[i][j]，表示将区间[i,j]分成若干个连续的非空子段所需的最小和。
初始状态下，所有的f[i][j]都未计算过，用-1表示。然后，我们开始递归计算每个f[i][j]的值。
j
|
0 1 2 3 4 5
0 | 0 -1 -1 -1 -1 -1
1 |-1 0 -1 -1 -1 -1
2 |-1 -1 0 -1 -1 -1
3 |-1 -1 -1 0 -1 -1
4 |-1 -1 -1 -1 0 -1
5 |-1 -1 -1 -1 -1 0
上面的表格表示了初始状态下的二维数组f。其中，f[i][j]表示将区间[i,j]分成若干个连续的非空子段所需的最小和，初始值都为-1。
接下来，我们通过递归计算并填充f数组。在计算过程中，我们会填充一些中间状态的结果，这里用数字表示：
j
|
0 1 2 3 4 5
0 | 0 -1 -1 -1 -1 -1
1 |-1 0 4 10 18 27
2 |-1 -1 0 6 15 26
3 |-1 -1 -1 0 7 19
4 |-1 -1 -1 -1 0 9
5 |-1 -1 -1 -1 -1 0
相当于是v的地址就是f[i][j]的地址，对v做改变，就是对f[i][j]做改变，实现了“记忆”
“记忆”不是这么体现的吧
=> -> =) -> =| -> =( -> =<
记忆化搜索不对，改成这样就行了。
int dfs(int i,int j)
{
if(i==j){//判断边界
f[i][j]=0;
return 0;
}
int v=f[i][j];
if(v!=-1) return v;
}
写的一样呀 服了你 楼主的记忆化搜索是对的
你这样写其实也没有毛病
但是没啥区别呀
整个局部变量给我看笑了，大家别被误导了
我想问一下i≤k≤j−1中为什么是j-1而不是j？
因为k是左半段的结尾，[k + 1, j]是右半段，k + 1必须<= j
为什么改成j也对啊
因为你已经把f[i][j]赋值为最大值，最小值与最大值中取Min还是取最小值
记忆化搜索里面，f的作用是什么呀，感觉没有用到它呀
为什么还要枚举区间长度啊？搞不懂。他不应该只有一个k分界就行了吗？这个区间长度拿来干什么？
为什么还要枚举区间长度啊？搞不懂
这个模板帅
怎么判断一道题是不是区间dp啊
老哥建议下面的 } 写一下对应的 { 的位置，这样代码更易读些
图解呢？
赞！