石子合并

石子合并是区间 DP 的经典问题.

例题

石子合并-acwing

石子合并-acwing

状态分析

区间 DP 状态通常使用 f(i, j) 来代表从 i 到 j 的一段区间的状态集合.

本题中, 我们用 f(i, j) 来表示合并区间 i ~ j 所需的代价, 属性为 MIN.

那么 f(i, j) 可以由如下状态转换: $k \in (i, j)$, f(i, j) = min(f(i, k) + f(k + 1, j) + s[j] - s[i - 1]), s[i] 为前 i 个元素的前缀和.

public class acwing_282 {

    static int N = 310;
    static int[] s = new int[N];
    static int[][] f = new int[N][N];

    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(reader.readLine().trim());

        String[] nums = reader.readLine().split(" ");
        for (int i = 1; i <= n; i++) {
            s[i] = Integer.parseInt(nums[i - 1]);
            s[i] += s[i - 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] = Integer.MAX_VALUE;
                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]);
    }
}

区间 DP 通用模板

        // 枚举区间长度
        for (int len = 2; len <= n; len++) {
            // 枚举起点
            for (int i = 1; i + len - 1 <= n; i++) {
                // 区间终点
                int j = i + len - 1;
                // ...
            }
        }