区间DP

什么是区间DP

• 区间DP是线性动态规划的扩展。它在分阶段的划分问题，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大关系
• F[i][j]：表示将下标 i 到 j 的所有元素合并能获得的价值的最大值

• 状态转移方程： cost是将这两组元素合并起来的代价

  特点

• 合并：即将两个或多个部分进行整合，当然也可以反过来

• 特征：能将问题分解为能两两合并的形式

• 求解：对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值

  例题：https://loj.ac/p/10147

• 题目概要：在一个环上有 n个数 a1, a2, a3 … ，进行 n-1 次合并操作，每次操作将相邻的两堆合并成一堆，能获得新的一堆中的石子数量的和的得分。你需要最大化你的得分。

• 先考虑在一条链上的情况
• dp状态：dp[i][j] 表示区间 [i, j] 内所有石子合并到一起的最大得分
• 状态转移方程：

• 将a数组的部分和转换为前缀和形式

• 状态转移：计算 F[i][j] 需要 F[i][k] 和 F[k+1][j] 的值，而这两个中包含的元素个数都小于 F[i][j] ，所以以len = j - i + 1 作为DP的阶段。首先从小到大枚举len，然后枚举 i 的值，根据len和i用公式计算出 j 的值，然后枚举 k ,时间复杂度 为 O(n^3)

• 处理环：将线延长两倍，变成 2 * n 堆，第 i 堆与第 n + i 堆相同，用动态规划求解后，取 F[0][n-1]，F[1][n] , ….中的最优值，即为最后的答案

• 最大值的代码

  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int[] nums = new int[2 * n];
    int[] sum = new int[2 * n];
    for (int i = 0; i < n; i++) {
        nums[i] = scanner.nextInt();
        nums[i + n] = nums[i];
    }
    sum[0] = nums[0];
    for (int i = 1; i < 2 * n; i++) {
        sum[i] = sum[i - 1] + nums[i];
    }
    //dp[i][j] = max(dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1])
    //dp[0][n-1]      len = j - i + 1
    int[][] dp = new int[2 * n][2 * n];
    for (int len = 1; len <= n; len++) {
        for (int i = 0; i < 2 * n; i++) {
            int j = len + i - 1;
            for (int k = i; k < j && j < 2 * n; k++) {
                int num = dp[i][k] + dp[k + 1][j] + sum[j];
                num = (i == 0) ? num : num - sum[i - 1];
                dp[i][j] = Math.max(dp[i][j], num);
            }
        }
    }
    int max = 0;
    for (int i = 0; i < n; i++) {
        if (max < dp[i][i + n - 1]) {
            max = dp[i][i + n - 1];
        }
    }
    System.out.println(max);
  }