区间DP + 暴力枚举 + 前缀和：堆石子

谁借莪１个温暖的怀抱￠ 2023-10-06 20:47 52阅读 0赞

## 区间DP + 暴力枚举 + 前缀和：堆石子 ##

#### 文章目录 ####

*  区间DP + 暴力枚举 + 前缀和：堆石子
 *   *   *  问题
         *  思路
         *  代码

#### 问题 ####

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 1]

#### 思路 ####

首先要注意每次只能合并相邻的石子，没有相邻这个限制就是一个简单的Huffman树贪心问题，有相邻的条件限制就变成了一个经典的区间DP问题  
  我们将石子的排列看作一个区间，题目要我们求合并n个石子的最小费用，可以看成是求合并区间\[1,n\]内石子所需最小花费。我们可以定义状态DP\[l\]\[r\]表示合并区间\[l,r\]上的石堆的最小花费。而DP\[l\]\[r\]是如何经状态转移得到的呢？注意到我们如果要合并区间\[l,r\]，那么我们最后肯定会得到两堆石子，这两堆石子分别是由\[l,r\]中两个不同区间合并得到的，我们最后再合并这两堆石子，DP\[l\]\[r\]就得到了。也就是说我们可以将\[l,r\]再分为两个子区间，DP\[l\]\[r\]由这两个子区间合并得到。  
  设我们将\[l,r\]区间分成了两个子区间\[l,k\]，\[k + 1,r\]。k的取值范围为`l <= k < r`，那么我们得到状态转移方程：  
  `DP[l][r] = min{DP[l][r]，DP[l][k] + DP[k + 1][r] + sum[l ~ r]}`  
  上述状态转移方程表示DP\[l\]\[r\]等于合并第一个子区间的费用DP\[l\]\[k\]加上合并第二个子区间的费用DP\[k+1\]\[r\]，再加上最后一次合并两个石堆的费用（等于区间sum和）。由于我们可以对\[l,r\]区间进行不同的划分，我们需要求出结果最小的划分，故加入了min函数更新最小值  
  对于DP\[i\]\[i\]，表示区间内只有一个元素，合并的费用为0，即DP\[i\]\[i\] = 0，而DP数组其他元素的初始值为INF。  
  接下来我们来看如何在程序中求解DP数组，对于上述DP数组的初始值，只有DP\[i\]\[i\] = 0是可以开启状态转移的，我们不能按左端点进行遍历，那样是求不出状态的，根据状态转移方程的思路，我们若要求合并大区间的费用，必须先求出小区间内合并的费用，为了求解DP数组，我们只能对区间长度从小到大进行枚举（第一层循环），接下来枚举左端点（第二层循环），根据左端点和长度计算出右端点，接着进行状态转移过程枚举分界点即k（第三层循环）。  
  状态转移方程中的区间和用前缀和数组实现即可。

#### 代码 ####

import java.util.*;
    
    public class Main {
        
        static int[][] dp = new int[305][305];
        static int[] preSum = new int[305];
        static int INF = 100000000;
        public static void main(String[] args) {
        
            int n, i, len, j, k;
            Scanner scanner = new Scanner(System.in);
            while (scanner.hasNextInt()) {
        
                n = scanner.nextInt();
                for (i = 1;i <= n;i++) {
        
                    preSum[i] = preSum[i - 1] + scanner.nextInt();
                    Arrays.fill(dp[i], INF);
                    dp[i][i] = 0;
                }
                for (len = 2; len <= n; len++) {
        
                    for (i = 1; i <= n - len + 1; i++) {
        
                        j = i + len - 1;
                        for (k = i; k < j; k++) {
        
                            dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + preSum[j] - preSum[i - 1]);
                        }
                    }
                }
                System.out.println(dp[1][n]);
            }
        }
    }

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/1989ebdd62d64288a6c05aa3bccc619a.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/0a79e6770e424641bcf1e32e251267ae.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16