$$\color{Red}{石子合并 详细题解}$$
这里附带打个广告——————我做的所有的题解
包括基础提高以及一些零散刷的各种各样的题
题目介绍
设有 N 堆石子排成一排，其编号为 1，2，3，…，N。
每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。
每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。
例如有 4 堆石子分别为 1 3 5 2， 我们可以先合并 1、2 堆，代价为 4，得到 4 5 2， 又合并 1，2 堆，代价为 9，得到 9 2 ，再合并得到 11，总代价为 4+9+11=24；
如果第二步是先合并 2，3 堆，则代价为 7，得到 4 7，最后一次合并代价为 11，总代价为 4+7+11=22。
问题是：找出一种合理的方法，使总的代价最小，输出最小代价。
输入格式
第一行一个数 N 表示石子的堆数 N
第二行 N 个数，表示每堆石子的质量(均不超过 1000)。
输出格式
输出一个整数，表示最小代价。
数据范围
1≤N≤300
输入样例：
4
1 3 5 2
输出样例：
22
1.算法细节
- 本题和 合并果子为什么不同？
合并果子是选择任意两堆合并，而合并石子是只能相邻的合并，因此不能利用哈夫曼树的思路去用贪心解题
- 以什么来判断我们需要用到所谓的区间DP？
最开始我们并不知道这道题是区间DP，但我们很容易想到以dp[i][j]来表示：从第i堆到第j堆石子合并所花最小代价的状态表达式，同时属性为最小值。
- 那么如何构造我们的状态方程呢？
显然，合并操作每次最终总会划分为两堆的合并，最后化为一个表达式，这个表达式的结果可以构造为dp[i][j] = dp[i][k] + dp[k+1][j] + s[j] - s[i-1]
这么顺畅的下去，我们岂不是就化作了一个简单的动态规划，只需要两层for循环：
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
-------
- 然后利用这个表达式，加上特判情况，岂不是就解决了问题？
当然不对
DP问题，在分析递推式最重要的，在01背包与完全背包的区分即可看出，我们首要考虑的是前一个状态
到底是不是在这个应有的循环条件下已经算出并且不会污染。
举例分析：dp[1][3] 的源头：dp[1][1] + dp[2][3] dp[1][2] + dp[3][3]
以我们线性DP的逻辑。只能先算出dp[1][n]才会去算dp[2][n],然而这种时候正常的线性dp就失效了
怎么样可以保证每次先把这些包含在其中一段段长度不一的表达式先算出来，还不会被污染呢？
区间DP闪亮登场
区间DP模板代码
for (int len = 1; len <= n; len++) // 先枚举区间长度算出内部作为基础
{
for (int i = 1; i + len - 1 <= n; i++) // 枚举起点，极限起点位置由区间长度和起点位置决定
{
int j = i + len - 1;// 区间终点
if (len == 1) { // 区间长度为1一般可以赋初始值
dp[i][j] = 初始值
continue;
}
// 枚举分割点，构造状态转移方程 i <= k < j!
for (int k = i; k < j; k++)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i][j]);
}
}
以前只是大概背下模板，但是没能理解流程，这里具体进入代码举例子：f[1][10] = max(f[1][2] + f[3][10] + f[1][3] + f[4][10] .....)，我们想算f[1][10]需要先把内部的都算出来，算内部又是相同的，需要先算内部，这样我们就递归的先递归到最内部，从区间长度为1开始，把f[1][2],f[2][3]等算出，然后再去增加区间长度，算f[1][3], f[2][4]等，最后一步步就可以算长的区间了
2.具体代码
java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static int N = 310, n;
static int[] s = new int[N];
static int[][] f = new int[N][N];
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
n = Integer.parseInt(br.readLine());
String[] s1 = br.readLine().split(" ");
for (int i = 1; i <= n; i++) {
int x = Integer.parseInt(s1[i - 1]);
s[i] = s[i - 1] + x;
Arrays.fill(f[i], 0x3f3f3f3f);
}
//区间DP
for (int len = 1; len <= n; len++) {
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
if(len == 1) f[i][j] = 0;
for (int k = i; k < j; k++) {
f[i][j] = Math.min(f[i][j], f[i][k] + f[k+1][j] + s[j] - s[i+1]);
}
}
}
System.out.println(f[1][n]);
}
}
python3
n = int(input())
f = [[0] * (n+10) for i in range(n+10)]
a = [0] + [int(x) for x in input().split()]
s = [0] * (n+10)
for i in range(1, n+1):
s[i] = s[i-1] + a[i]
#区间DP
# 区间长度
for len in range(2, n+1):
# 起点
i = 1
while i + len - 1 <= n:
l = i
r = i + len - 1
f[l][r] = 1e9
# 划分区间切割点
for k in range(l, r):
f[l][r] = min(f[l][r], f[l][k] + f[k+1][r] + s[r] - s[l-1])
# 更新起点值
i += 1
print(f[1][n])
C++
#include <iostream>
#include <cstring>
using namespace std;
const int N = 310;
int a[N], s[N];
int dp[N][N];
int main()
{
int n;
cin >> n;
for(int i=1; i<=n; i++) scanf("%d", &a[i]), s[i] += s[i-1] + a[i];
//求最小值，所以先把表达式化为无穷
memset(dp, 0x3f, sizeof dp);
//区间化DP模板
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] = 0;
continue;
}
for(int k=i; k<j; k++)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + s[j] - s[i-1]);
}
}
cout << dp[1][n] << endl;
return 0;
}
