区间DP + 暴力枚举 + 前缀和:堆石子
文章目录
问题
思路
首先要注意每次只能合并相邻的石子,没有相邻这个限制就是一个简单的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]);
}
}
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/153721.html