算法面试真题详解:石子归并

简介: 算法面试真题详解:石子归并

有一个石子归并的游戏。最开始的时候,有n堆石子排成一列,目标是要将所有的石子合并成一堆。合并规则如下:

  1. 每一次可以合并相邻位置的两堆石子
  2. 每次合并的代价为所合并的两堆石子的重量之和
    求出最小的合并代价。

在线评测地址:领扣题库官网

样例 1:

输入: [3, 4, 3]
输出: 17

样例 2:

输入: [4, 1, 1, 4]
输出: 18

解释:

  1. 合并第二堆和第三堆 => [4, 2, 4], score = 2
  2. 合并前两堆 => [6, 4],score = 8
  3. 合并剩余的两堆 => [10], score = 18

算法:区间DP

这是一道区间DP问题,我们需要用区间表示状态来递推。

更多DP算法真题详解,点此免费查看

设s是表示石头重量的数组,设fi是将s[i,...,j]的石头合并成一个所需的最少能量,那么这个最少能量按照最后一步合并的分界线可以分为以下几种情况:
1、最后一步是s[i]和s[i+1,...,j]合并,此时需要的最少能量是fi+1+sum(s[i]...s[j]),第一项是合并后者需要的能量,第二项是最后一次合并所需要的能量。s[i]自己只有一个石头,不需要合并
2、最后一步是s[i,i+1]和s[i+2,...,j]合并,此时需要的最少能量是fi+fi+2+sum(s[i]...s[j]),第一项是合并前两个石头需要的能量,第二项是合并后半区间石头需要的能量,最后一项是最后一次合并需要的能量;
从上面我们可以看出一个规律,fi应该是所有区间分法中前一半区间的石头合并需要的总能量加上后半区间的总能量再加上最后一次合并需要的能量

  • 求得A的前缀和
  • 区间长度从2开始枚举,
  • 根据上诉思路可得递推式
  • dpl =min(dpl, dpl + dpj + 1 + sum_a[r + 1] - sum_a[l])
  • 记得初始化dpl为一个较大值
  • 结果存在dp0中

复杂度分析

  • 时间复杂度O(n^3)

    • 区间dp的复杂度
  • 空间复杂度O(n^2)

    • dp数组的大小
public class Solution {
    /**
     * @param A: An integer array
     * @return: An integer
     */
    public int stoneGame(int[] A) {
        int size = A.length;
        if (A == null || size == 0) {
            return 0;
        }
        
        int[][] dp = new int[size][size];
        int[] sum_a = new int[size + 1];
        //前缀和
        for (int i = 0; i < size; i++) {
            sum_a[i + 1] = sum_a[i] + A[i];
        }
        // 长度从2开始即可,因为长度为1的时候结果是0,dp初始化的时候默认就是0,没必要赋值
        for (int len = 2; len <= size; len++) {
            // i枚举的是正在枚举的区间的左端点
            for (int i = 0; i + len - 1 < size; i++) {
                // 正在枚举的区间左端点是i,右端点是i + size - 1
                int l = i, r = i + len - 1;
                // 在求最小的时候,需要初始化成一个很大的数,然后不断更新
                dp[l][r] = Integer.MAX_VALUE;
                for (int j = l; j < r; j++) {
                    //递推式
                    dp[l][r] = Math.min(dp[l][r], dp[l][j] + dp[j + 1][r] + sum_a[r + 1] - sum_a[l]);
                }
            }
        }
        
        return dp[0][size-1];
    }
}

更多题解参考:九章官网solution

相关文章
|
11天前
|
搜索推荐 C++ Python
Python排序算法大PK:归并VS快速,谁才是你的效率之选?
【7月更文挑战第13天】归并排序** 使用分治法,稳定且平均时间复杂度O(n log n),适合保持元素顺序和并行处理。
14 5
|
14天前
|
算法 Java
Java面试题:解释垃圾回收中的标记-清除、复制、标记-压缩算法的工作原理
Java面试题:解释垃圾回收中的标记-清除、复制、标记-压缩算法的工作原理
21 1
|
1月前
|
消息中间件 算法 Java
抖音面试:说说延迟任务的调度算法?
Netty 框架是以性能著称的框架,因此在它的框架中使用了大量提升性能的机制,例如 Netty 用于实现延迟队列的时间轮调度算法就是一个典型的例子。使用时间轮调度算法可以实现海量任务新增和取消任务的时间度为 O(1),那么什么是时间轮调度算法呢?接下来我们一起来看。 ## 1.延迟任务实现 在 Netty 中,我们需要使用 HashedWheelTimer 类来实现延迟任务,例如以下代码: ```java public class DelayTaskExample { public static void main(String[] args) { System.ou
33 5
抖音面试:说说延迟任务的调度算法?
|
14天前
|
算法 Java 程序员
Java面试题:解释Java的垃圾回收机制,包括常见的垃圾回收算法。介绍一下Java的垃圾回收算法中的标记-压缩算法。
Java面试题:解释Java的垃圾回收机制,包括常见的垃圾回收算法。介绍一下Java的垃圾回收算法中的标记-压缩算法。
17 0
|
14天前
|
算法 Java 开发者
Java面试题:Java内存探秘与多线程并发实战,Java内存模型及分区:理解Java堆、栈、方法区等内存区域的作用,垃圾收集机制:掌握常见的垃圾收集算法及其优缺点
Java面试题:Java内存探秘与多线程并发实战,Java内存模型及分区:理解Java堆、栈、方法区等内存区域的作用,垃圾收集机制:掌握常见的垃圾收集算法及其优缺点
16 0
|
14天前
|
存储 算法 Java
Java面试题:解释JVM的内存结构,并描述堆、栈、方法区在内存结构中的角色和作用,Java中的多线程是如何实现的,Java垃圾回收机制的基本原理,并讨论常见的垃圾回收算法
Java面试题:解释JVM的内存结构,并描述堆、栈、方法区在内存结构中的角色和作用,Java中的多线程是如何实现的,Java垃圾回收机制的基本原理,并讨论常见的垃圾回收算法
12 0
|
1月前
|
存储 算法 Java
面试高频算法题汇总「图文解析 + 教学视频 + 范例代码」之 二分 + 哈希表 + 堆 + 优先队列 合集
面试高频算法题汇总「图文解析 + 教学视频 + 范例代码」之 二分 + 哈希表 + 堆 + 优先队列 合集
|
2月前
|
机器学习/深度学习 算法 固态存储
深度学习算法工程师面试问题总结| 深度学习目标检测岗位面试总结
本文给大家带来的百面算法工程师是深度学习目标检测岗位面试总结,文章内总结了常见的提问问题,旨在为广大学子模拟出更贴合实际的面试问答场景。在这篇文章中,我们还将介绍一些常见的深度学习目标检测面试问题,并提供参考的回答及其理论基础,以帮助求职者更好地准备面试。通过对这些问题的理解和回答,求职者可以展现出自己的深度学习目标检测领域的专业知识、解决问题的能力以及对实际应用场景的理解。同时,这也是为了帮助求职者更好地应对深度学习目标检测岗位的面试挑战,提升面试的成功率和竞争力。
|
1月前
|
数据采集 算法 数据挖掘
LeetCode 题目 80:删除排序数组中的重复项 II【算法面试高频题】
LeetCode 题目 80:删除排序数组中的重复项 II【算法面试高频题】
|
1月前
|
算法 C语言
数据结构和算法——归并排序(有序子列的归并、递归算法、非递归算法、思路图解、C语言代码)
数据结构和算法——归并排序(有序子列的归并、递归算法、非递归算法、思路图解、C语言代码)
16 0

热门文章

最新文章