「区间DP-步入」石子合并（简单版）

石子合并（简单版）

题目描述

设有 $N(N\le 300)$ 堆石子排成一排，其编号为 $1,2,3,\cdots ,N$。每堆石子有一定的质量 m i ( m i ≤ 1000 ) m_i(m_i \\le 1000) mi​(mi​≤1000)。现在要将这 N 堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻。合并时由于选择的顺序不同，合并的总代价也不相同。试找出一种合理的方法，使总的代价最小，并输出最小代价。

输入格式

第一行，一个整数 N
第二行，N 个整数 m i m_i mi​

输出格式

输出文件仅一个整数，也就是最小代价。

样例

4
4 5 9 4

44

说明

• https://www.luogu.com.cn/problem/P1775

解析

首先缩小问题规模：

• 一个数字时：无需合并
• 两个数字时：$[4,5]$ 合并得 9
• 三个数字时：$[4,5,9]$ 合并得到 $(4+5)+9=9+9=18$ 或 $4+(5+9)=4+14=18$

由上可知，我们应该以 len 递增的形式分割区间。

区间和，可以通过前缀和预处理来实现。

DP 信息：

• 原问题：找到一定顺序进行相邻石子的合并，使其最后的代价最小
• 子问题：$[i][j]$ 求出 i 到 j 之间石子合并的最小代价
• DP 定义：$dp[i][j]$ 表示 i 到 j 之间石子合并的最小代价
• DP 方程：$dp[i,j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1])$
• DP 边界：$dp[i][j]=INF$ 、$dp[i][i]=0$

代码

public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[] F = new int[n+1];int[][] dpMin = new int[n+1][n+1];int[] sum = new int[n+1];final int INF = 1 << 30;for(int i = 0; i <= n; i++) Arrays.fill(dpMin[i], INF); // INFfor(int i = 1; i <= n; i++) {F[i] = sc.nextInt();sum[i] = sum[i-1] + F[i]; // 预处理前缀和dpMin[i][i] = 0; // 自己与自己无法合并}for(int len = 2; len <= n; len++) { // 枚举区间for(int i = 1; i <= n - len + 1; i++) { // 枚举区间起点int j = i + len - 1; // 计算区间终点for(int k = i; k < j; k++) { // 枚举分界点dpMin[i][j] = Math.min(dpMin[i][j], dpMin[i][k] + dpMin[k+1][j] + sum[j] - sum[i-1]);}}}System.out.print(dpMin[1][n]);}
}