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

梦想不抛弃苦心追求的人,只要不停止追求,你们会沐浴在梦想的光辉之中。再美好的梦想与目标,再完美的计划和方案,如果不能尽快在行动中落实,最终只能是纸上谈兵,空想一番。只要瞄准了大方向,坚持不懈地做下去,才能够扫除挡在梦想前面的障碍,实现美好的人生蓝图。区间DP + 暴力枚举 + 前缀和:堆石子,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com,来源:原文

区间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

(0)
飞熊的头像飞熊bm

相关推荐

发表回复

登录后才能评论
极客之音——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!