当前位置： 首页 > article >正文

动态规划：石子合并 图文+举例超详细说明

article 2024/12/26 1:11:18

目录

一、题目描述

二、解题思路

1、minCost和maxCost数组的含义

2、minCost和maxCost数组的递推公式

3、minCost和maxCost数组的初始化

4、遍历顺序

5、举例推导数组

（1）初始化

（2）遍历构建minCost[i][j]和maxCost[i][j]表

（3）遍历数组，查找并比较子串长度为N（[0][3]、[1][0]、[2][1]、[3][2]）的最大值

三、完整代码

一、题目描述

在一个圆形操场的四周摆放 N 堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的 2 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。

试设计出一个算法,计算出将 N 堆石子合并成 1 堆的最小得分和最大得分。

输入格式:

数据的第 1 行是正整数 N ，表示有 N 堆石子。

第 2 行有 N 个整数，第 i 个整数 ai​ 表示第 i 堆石子的个数。

输出格式:

输出共 2 行，第 1 行为最小得分，第 2 行为最大得分。

输入样例:

4
4 5 9 4

输出样例:

43
54

二、解题思路

题目描述中说是在一个圆形操场，那我们就要考虑石子堆是环形的情况，也就是说，石子堆首尾相连。在解题时，我们就可以考虑用2N的线性数组int[] extendedStones = new int[2 * N];来表示环形首尾相接的石子堆。

// 复制一份石头堆数组以处理环形结构
int[] extendedStones = new int[2 * N];
for (int i = 0; i < 2 * N; i++) {
     extendedStones[i] = stones[i % N];
}

合并的得分，我们可以通过计算前缀和int[] prefixSum = new int[2 * N + 1]来获得（prefixSum[ 3 ] = stones[ 0 ] + stones[ 1 ] + stones[ 2 ] ，不包括stones[ 3 ]） 。例如：相邻的第 i 堆石子和第 j 堆石子合并的得分cost  = prefixSum[ j+1 ] - prefixSum[ i ] 。

int[] prefixSum = new int[2 * N + 1];
for (int i = 1; i <= 2 * N; i++) {
     prefixSum[i] = prefixSum[i - 1] + extendedStones[i - 1];
}

但是，对于记录最小得分和最大得分的二维数组minCost和maxCost，它们的大小只需[N][N]就足够了。（具体解释看下面含义）

1、minCost和maxCost数组的含义

minCost[ i ][ j ]表示将从索引 i 到索引 j 的石子堆合并成一堆的最小得分。

maxCost[ i ][ j ]表示将从索引 i 到索引 j 的石子堆合并成一堆的最大得分。

对于记录最小得分和最大得分的二维数组：我们实际上只需要考虑长度为 N 的子序列，因此这些表格的大小为 [N][N]就足够了。

2、minCost和maxCost数组的递推公式

要求最小得分和最大得分，意味着我们要找到：怎样分割石子堆能使石子堆合并得到最小得分和最大得分。

根据minCost和maxCost数组的含义，我们可以利用动态规划先解决子问题的思想以 k 为分割点找到所有的分割方法，再从中比较分别选取最小值和最大值即可，即

 for (int k = i; (k % N) != j; k++) { // 分割点
        int cost = prefixSum[i + len] - prefixSum[i]; // 合并得分,i + len是此时j在prefixSum中的位置
        minCost[i][j] = Math.min(minCost[i][j], 
                        minCost[i][(k % N)] + minCost[(k + 1) % N][j] + cost);
        maxCost[i][j] = Math.max(maxCost[i][j], 
                        maxCost[i][(k % N)] + maxCost[(k + 1) % N][j] + cost);
}

3、minCost和maxCost数组的初始化

因为单独的一堆石子无法合并，没有最小或最大得分，所以minCost[i][i]和maxCost[i][i]初始化为0（也就是对角线）。而由递推公式可知，其他情况合并的得分都由子问题计算覆盖得来，也都可以初始化为0.

int[][] minCost = new int[N][N];
int[][] maxCost = new int[N][N];

但由于后面是通过比较大小来更新minCost和maxCost数组，所以要在比较前赋值为

minCost[i][j] = Integer.MAX_VALUE;//初始化
maxCost[i][j] = Integer.MIN_VALUE;//初始化

4、遍历顺序

由递推公式可知，当前的minCost[i][j]和maxCost[i][j]是依赖于其子问题的值，也就是依赖于子问题长度比当前的minCost[i][j]和maxCost[i][j]的子问题长度小的值。所以要先由长度小的子问题开始遍历。

先遍历子问题长度，首先解决所有子问题长度len为2（也就是两堆石子堆）的问题，然后是子问题长度len为3的，依此类推，直到解决N个石子堆的问题。

在每种子问题长度len的情况中再嵌套截取不同起始位置 i 和终止位置 j 的子问题（这里的起始位置 i 是在原始石子堆数组stone中，取0~(N-1)作为每种可能的起始位置，以避免重复计算；对于 j 的值我们需其对N取余，确保当 j 到达数组末尾N时，会自动回到数组开头，以此来实现首尾相连）。

而对于每种长度为 len 的情况，又有很多种合并方式，于是将其内部以 k 为分割点来分割成两小部分，把这两小部分的最小（最大）得分相加，再加上把这两部分合并得到的得分cost，就能得到当前的最小minCost[i][j]（最大maxCost[i][j]）。也就是嵌套三重循环。确保找出所有的合并方式。

for (int len = 2; len <= N; len++) { // 子问题长度
    for (int i = 0; i < N; i++) {
        int j = ( i + len - 1 ) % N ;
        minCost[i][j] = Integer.MAX_VALUE;//初始化
        maxCost[i][j] = Integer.MIN_VALUE;//初始化
        for (int k = i; (k % N) != j; k++) { // 分割点
        int cost = prefixSum[i + len] - prefixSum[i]; // 合并得分,i + len是此时j在prefixSum中的位置
        minCost[i][j] = Math.min(minCost[i][j], 
                        minCost[i][(k % N)] + minCost[(k + 1) % N][j] + cost);
        maxCost[i][j] = Math.max(maxCost[i][j], 
                        maxCost[i][(k % N)] + maxCost[(k + 1) % N][j] + cost);
        }
    }
}

(k % N) 和 ((k + 1) % N) 确保了分割点 k 和 k+1 始终在 [0, N-1] 范围内，即使 k 超过了 N

（不是很能理解的看后面第5点的图文举例解释，标黄部分在第5点同样标黄部分有图文举例解释）

5、举例推导数组

有N=4堆石子，每堆石子个数为4,5,9,4。

（1）初始化

minCost[i][j]和maxCost[i][j]的值均为0.

（2）遍历构建minCost[i][j]和maxCost[i][j]表

递推公式：

int cost = prefixSum[i + len] - prefixSum[i];

minCost[i][j] = Math.min(minCost[i][j], minCost[i][(k % N)] + minCost[(k + 1) % N][j] + cost);
maxCost[i][j] = Math.max(maxCost[i][j], maxCost[i][(k % N)] + maxCost[(k + 1) % N][j] + cost);

  • 子问题长度为len=2时的划分情况有4种：

        （1）i=0,j=1

minCost[0][1] = Integer.MAX_VALUE;
maxCost[0][1] = Integer.MIN_VALUE;

        以k(int k = i; (k % N) != j; k++)为分割点进行分割（此时子问题长度为2的分割可能不太能体现k分割的作用，子问题长度为3的较明显）。

①k=0: 分为[0][0]和[1][1]两小部分，这两小部分的最小得分和最大得分均为0，再计算将这两堆石子合并为一堆的得分cost=4+5，即minCost[0][0] + minCost[1][1] + cost=0+0+（4+5）=9，maxCost同理。而minCost[0][1]=Integer.MAX_VALUE，maxCost[0][1]=Integer.MIN_VALUE，所以比较可得minCost[0][1]=9，maxCost[0][1]=9。

     

        （2）i=1,j=2

      同理，略

         minCost[1][2]=14，maxCost[1][2]=14。

        （3）i=2,j=3

minCost[2][3] = Integer.MAX_VALUE;
maxCost[2][3] = Integer.MIN_VALUE;

  以k(int k = i; (k % N) != j; k++)为分割点进行分割。

①  k=2: 分为[2][2]和[3][3]两小部分，这两小部分的最小得分和最大得分均为0，再计算将这两堆石子合并为一堆的得分cost=9+4，即minCost[2][2] + minCost[3][3] + cost=0+0+（9+4）=13，maxCost同理。而minCost[2][3]=Integer.MAX_VALUE，maxCost[2][3]=Integer.MIN_VALUE，所以比较可得minCost[2][3]=13，maxCost[2][3]=13。

        （4）i=3,j=0（当i以3为起始位置时，子串长度为2，j如果不对N进行取余（j=5），将会超出数组最大下标3，取余之后会回到数组首部（j=0），以此实现首尾相连）

minCost[3][0] = Integer.MAX_VALUE;
maxCost[3][0] = Integer.MIN_VALUE;

①  k=3: 分为[3][3]和[0][0]两小部分，这两小部分的最小得分和最大得分均为0，再计算将这两堆石子合并为一堆的得分cost=4+4，即minCost[3][3] + minCost[0][0] + cost=0+0+（4+4）=8，maxCost同理。而minCost[3][0]=Integer.MAX_VALUE，maxCost[3][0]=Integer.MIN_VALUE，所以比较可得minCost[3][0]=8，maxCost[3][0]=8。

子问题长度为len=2时的划分情况结束，如果 i 再往后遍历就会重复计算4和5这两堆石子，所以i<N

  • 子问题长度为len=3时的划分情况有4种：

        （1）i=0,j=2

minCost[0][2] = Integer.MAX_VALUE;
maxCost[0][2] = Integer.MIN_VALUE;

①k=0：分为[0][0]和[1][2]两小部分，这两小部分minCost[0][0]=0，maxCost[0][0]=0，minCost[1][2]=14，maxCost[1][2]=14，再计算将这两堆石子合并为一堆的得分cost=4+（5+9），即minCost[0][0] + minCost[1][2] + cost=0+14+（4+5+9）=32，maxCost同理。而minCost[0][2]=Integer.MAX_VALUE，maxCost[0][2]=Integer.MIN_VALUE，所以比较可得minCost[0][2]=32，maxCost[0][2]=32。

②k=1：分为[0][1]和[2][2]两小部分，这两小部分minCost[0][1]=9，maxCost[0][1]=9，minCost[2][2]=0，maxCost[2][2]=0，再计算将这两堆石子合并为一堆的得分cost=（4+5）+9，即minCost[0][1] + minCost[2][2] + cost=0+9+（4+5+9）=27，maxCost同理。而minCost[0][2]=32，maxCost[0][2]=32，所以比较可得minCost[0][2]=27，maxCost[0][2]=32。

        （2）i=1,j=3

minCost[1][3] = Integer.MAX_VALUE;
maxCost[1][3] = Integer.MIN_VALUE;

①k=1：分为[1][1]和[2][3]两小部分，这两小部分minCost[1][1]=0，maxCost[1][1]=0，minCost[2][3]=13，maxCost[2][3]=13，再计算将这两堆石子合并为一堆的得分cost=5+(9+4)，即minCost[1][1] + minCost[2][3] + cost=0+13+5+(9+4)=31，maxCost同理。而minCost[1][3]=Integer.MAX_VALUE，maxCost[1][3]=Integer.MIN_VALUE，所以比较可得minCost[1][3]=31，maxCost[1][3]=31。

②k=2：分为[1][2]和[3][3]两小部分，这两小部分minCost[1][2]=14，maxCost[1][2]=14，minCost[3][3]=0，maxCost[3][3]=0，再计算将这两堆石子合并为一堆的得分cost=(5+9)+4，即minCost[1][2] + minCost[3][3] + cost=14+0+(5+9)+4=32，maxCost同理。而minCost[1][3]=31，maxCost[1][3]=31，所以比较可得minCost[1][3]=31，maxCost[1][3]=32。

（3）i=2,j=0，略

minCost[2][0]=25，maxCost[2][0]=30

（4）i=3,j=1，略

minCost[3][1]=21，maxCost[3][1]=22

  • 子问题长度为len=4时的划分情况有4种：

（1）i=0,j=3

有3种分割情况：k=0、k=1、k=2

过程略

minCost[0][3]=44，maxCost[0][3]=54

（2）i=1,j=0

有3种分割情况：k=1、k=2、k=3

过程略

minCost[1][0]=44，maxCost[1][0]=54

（3）i=2,j=1

有3种分割情况：k=2、k=3、k=0

过程略

minCost[2][1]=43，maxCost[2][1]=52

（4）i=3,j=2

有3种分割情况：k=3、k=0、k=1

过程略

minCost[3][2]=43，maxCost[3][2]=54

（3）遍历数组，查找并比较子串长度为N（[0][3]、[1][0]、[2][1]、[3][2]）的最大值

// 查找最小值和最大值
int minScore = Integer.MAX_VALUE;
int maxScore = Integer.MIN_VALUE;
for (int i = 0; i < N; i++) {
    minScore = Math.min(minScore, minCost[i][(i + N - 1) % N]);
    maxScore = Math.max(maxScore, maxCost[i][(i + N - 1) % N]);
}

minScore=43，maxScore=54

三、完整代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();
        int[] stones = new int[N];
        for (int i = 0; i < N; i++) {
            stones[i] = scanner.nextInt();
        }

        System.out.println(minMaxMergeScore(stones, N));
        scanner.close();
}

    private static String minMaxMergeScore(int[] stones, int N) {
        // 复制一份石头堆数组以处理环形结构
        int[] extendedStones = new int[2 * N];
        for (int i = 0; i < 2 * N; i++) {
            extendedStones[i] = stones[i % N];
        }

        // 计算前缀和
        int[] prefixSum = new int[2 * N + 1];
        for (int i = 1; i <= 2 * N; i++) {
            prefixSum[i] = prefixSum[i - 1] + extendedStones[i - 1];
        }

        // 动态规划表格
        int[][] minCost = new int[N][N];
        int[][] maxCost = new int[N][N];

        // 动态规划填表
        for (int len = 2; len <= N; len++) { // 子问题长度
            for (int i = 0; i < N; i++) {
                int j = (i + len - 1) % N;
                minCost[i][j] = Integer.MAX_VALUE;
                maxCost[i][j] = Integer.MIN_VALUE;
                for (int k = i; (k % N) != j; k++) { // 分割点
                    int cost = prefixSum[i + len] - prefixSum[i]; // 合并得分
                    minCost[i][j] = Math.min(minCost[i][j],
                            minCost[i][(k % N)] + minCost[(k + 1) % N][j] + cost);
                    maxCost[i][j] = Math.max(maxCost[i][j],
                            maxCost[i][(k % N)] + maxCost[(k + 1) % N][j] + cost);
                }
            }
        }

        // 查找最小值和最大值
        int minScore = Integer.MAX_VALUE;
        int maxScore = Integer.MIN_VALUE;
        for (int i = 0; i < N; i++) {
            minScore = Math.min(minScore, minCost[i][(i + N - 1) % N]);
            maxScore = Math.max(maxScore, maxCost[i][(i + N - 1) % N]);
        }

        return minScore + "\n" + maxScore;
    }
}


http://www.kler.cn/a/451465.html

相关文章：

  • 【西安电子科技大学考研】25官方复试专业课参考书目汇总
  • 从 GitLab.com 到 JihuLab.com 的迁移指南
  • ubuntu安装sublime安装与免费使用
  • 选择FPGA开发，学历是硬性要求吗？
  • 2. SQL窗口函数使用
  • Odoo 免费开源 ERP：通过 JavaScript 创建对话框窗口的技术实践分享
  • OpenCV相机标定与3D重建(26)计算两个二维点集之间的部分仿射变换矩阵（2x3）函数 estimateAffinePartial2D()的使用
  • AWTK 在树莓派 pico 上的移植笔记
  • HTMLCSSJavaScriptDOM 之间的关系？
  • 组态页面渲染器通过npm包方式使用页面没有渲染成功的问题
  • gesp(三级)（14）洛谷：B4039：[GESP202409 三级] 回文拼接
  • 贪心算法求解加油站问题
  • 《ROS2 机器人开发 从入门道实践》 鱼香ROS2——第4章内容
  • WebAuthn 项目常见问题解决方案
  • C++抽象类与类继承相关注意事项 [学习笔记]
  • select 1 from table的作用 详解
  • 【ue5学习笔记2】在场景放入一个物体的蓝图输入事件无效？
  • sentinel学习笔记8-系统自适应与黑白名单限流
  • LabVIEW实现GSM/GPRS通信
  • LeetCode 3138.同位字符串连接的最小长度：计数（一个数最多128个因数）
  • Python中定位元素包含文本信息的详细解析与代码示例
  • QWebChannel实现与JS的交互
  • 使用React构建一个掷骰子的小游戏
  • skywalking 搭建
  • 【漫话机器学习系列】016.误差中的偏差(BIAS)
  • 【漏洞复现】CVE-2015-5531 Arbitrary File Reading