【区间 dp】A023_LC_合并石头的最低成本(穷举分割点)

一、Problem

有 N 堆石头排成一排,第 i 堆中有 stones[i] 块石头。

每次移动(move)需要将连续的 K 堆石头合并为一堆,而这个移动的成本为这 K 堆石头的总数。

找出把所有石头合并成一堆的最低成本。如果不可能,返回 -1 。

Input: stones = [3,2,4,1], K = 2
Output: 20
Explanation: 
We start with [3, 2, 4, 1].
We merge [3, 2] for a cost of 5, and we are left with [5, 4, 1].
We merge [4, 1] for a cost of 5, and we are left with [5, 5].
We merge [5, 5] for a cost of 10, and we are left with [10].
The total cost was 20, and this is the minimum possible.

Note:

1 <= stones.length <= 30
2 <= K <= 30
1 <= stones[i] <= 100

二、Solution

方法一:记忆化搜索

  • 定义状态
    • f[i][j][k]f[i][j][k] 表示将区间 [i,j][i, j] 中的几堆石子合并成 kk 堆需要的最小代价
  • 思考初始化:
    • f[0:][0:][0:]=INFf[0:][0:][0:] = INF
    • f[i][i][1]=0f[i][i][1] = 0 石子不用动就可以了…
  • 思考状态转移方程
    • 这里直接写转移会比较繁琐,所以直接讲思路:因为我们不知道合并哪些区间可以使得代价最小,所以我们需要穷举一下每种大小的区间 len(len = r-l+1)
    • 且在区间 [l, r] 中,我们也不清楚具体要合并哪两对堆(如果将区间划分成两半)所以我们需要枚举一下切分点 p 在区间 [l, r] 中的位置
    • 切分位置 p 我们知道了,但是我们还不知道要将这两部分石子合并成几堆,所以我们还需要枚举一下石子的对数 kkrl+1k(k \leqslant r-l+1)
  • 思考输出f[1][n][1]f[1][n][1]
class Solution {
    public int mergeStones(int[] a, int K) {
        int n = a.length, INF = 0x3f3f3f3f, s[] = new int[n+1], f[][][] = new int[n+1][n+1][n+1];
        if ((n-1) % (K-1) != 0)
            return -1;
        if (n < 2)
            return 0;
        for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            Arrays.fill(f[i][j], INF);
        }
        for (int i = 1; i <= n; i++) {
            s[i] = s[i-1] + a[i-1];
            f[i][i][1] = 0;
        }

        for (int len = 2; len <= n; len++)
        for (int l = 1; l <= n - len + 1; l++) {
            int r = l + len - 1;
            
            for (int k = 2; k <= len; k++)
            for (int p = l; p < r; p++) {
                f[l][r][k] = Math.min(f[l][r][k], f[l][p][k-1] + f[p+1][r][1]);
            }
            // 由于上面的k是递增的,所以到达K时,f[l][r][K]一定是最小(最优)此时
            f[l][r][1] = Math.min(f[l][r][1], f[l][r][K] + s[r] - s[l-1]); 
        }
        return f[1][n][1];
    }
}
复杂度分析
  • 时间复杂度:O(n3×K)O(n^3 × K)
  • 空间复杂度:O(n3)O(n^3)

热门文章

暂无图片
编程学习 ·

Spring学习笔记(一):工厂模式

Spring学习笔记一:工厂模式1.简介2.工厂模式简单工厂设计通⽤⼯⼚的设计通用工厂的使用方式 1.简介 1.Spring是⼀个轻量级的 JavaEE 解决⽅案,整合众多优秀的设计模式。 2.EJB(Enterprise Java Bean):重量级框架,存在问题包括:运行环境苛刻,代码移植性差。 什么是轻量级?…
暂无图片
编程学习 ·

Java使用poi将office文件转为html

一、前言 功能需求:上传office文档,并提供文件在线预览。 解决方案:使用Aspose.cells.jar包,将文档转换为pdf格式; 使用libreOffice,将文档转换为pdf格式; 使用poi将文档转换为html格式。方案一:通过Aspose的方式,该功能是付费版,需要破解,所以是能抛弃。 方案二,使…
暂无图片
编程学习 ·

二值化方法

一、全局阈值法1.固定阈值方法该方法是对于输入图像中的所有像素点统一使用同一个固定阈值。其基本思想如下:其中,T为全局阈值。缺点:很难为不同的输入图像确定最佳阈值。2.Otsu算法Otsu算法又称最大类间方差法先明确两个概念:(1)均值(2)方差图像的阈值化处理,就是将图像分为…
暂无图片
编程学习 ·

Promethus(普罗米修斯)监控系统搭建与使用实践

1.目标 1.1 能够安装prometheus服务器 1.2 能够通过安装node_exporter监控远程linux 1.3 能够通过安装mysqld_exporter监控远程mysql数据库 1.4 能够安装grafana 1.5 能够在grafana添加prometheus数据源 1.6 能够在grafana添加监控cpu负载的图形 1.7 能够在grafana图形显示mysq…
暂无图片
编程学习 ·

git命令大全

Git 是一个开源的分布式版本控制系统,用于敏捷高效地处理任何或小或大的项目。 Git 是 Linus Torvalds 为了帮助管理 Linux 内核开发而开发的一个开放源码的版本控制软件。 Git官方网站:https://git-scm.com/ 原理图Workspace:工作区 Index / Stage:暂存区 Repository:仓库…
暂无图片
编程学习 ·

爬虫工作的代理ip选择

代理ip的使用是爬虫工作必须使用的爬取辅助工具,大数据的快速发展,很多的网站不断的维护自己的网站信息,开始设置反爬虫机制,在网站进行反爬虫限制的情况下,怎样通过反爬虫机制,提高工作效率。一:使用多线程与代理ip1、多线程方式:多线程同时开展工作采集,迅速提高工作…
暂无图片
编程学习 ·

产品经理新人必看的避坑指南

产品经理的一路走来,会遇到大大小小的“坑”。从毕业开始做产品经理已有7年,一直在回想自己有哪些地方做的不够好需要改进的。趁自己闲暇时间总结分享出来,希望能给产品新人一些启示。 一、不问要求埋头苦干。 产品新人刚入职的时候,因为经验不足,不太熟悉业务,往往一开始…
暂无图片
编程学习 ·

【Linux】——I/O复用之poll

1、poll的概述 在上一篇文章中,我们详细的介绍了I/O复用技术中的select使用。这篇文章我们来主要介绍一下poll. poll系统调用和select类似,也是在指定事件内轮询一定数量的文件描述符,以测试其中是否有就绪的 本质都是统一监听,如果任意一个文件描述符上有关注的事件发生。…
暂无图片
编程学习 ·

剑指Offer 10-| 学习笔记

剑指Offer 10-| 学习笔记 写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项。斐波那契数列的定义如下: F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。 答案需要取模…
暂无图片
编程学习 ·

Vue——09——v-for和key指令

遍历普通数组 <!DOCTYPE html> <html lang="en"><head><meta charset="UTF-8"><meta name="viewport" content="width=device-width, initial-scale=1.0"><title>Document</title><scri…
暂无图片
编程学习 ·

Anuspline气象插值

Anuspline气象插值 收集两个帖子,做到是降水的插值 https://zhuanlan.zhihu.com/p/93957062 https://www.pianshen.com/article/29901140397/
暂无图片
编程学习 ·

硕彦博创李飞授-------计算机基础及C语言变量

一、计算机基础 计算机只能识别二进制; 1.存储单位 最小存储单位:bit(比特) ----- 存储 0和1 基本存储单位:byte(字节) ----- 1byte = 8bit 其他单位:理论上 1KB = 1024B 1MB = 1024KB 1GB= 1024MB 1TB = 1024 GB Ps: 工业上:1Gb = 1000Mb 2.数制位: 二进制:满2进1,…
暂无图片
编程学习 ·

kuangbin专题8 生成树 次小生成树部分 HDU4081/UVA10600/UVA10462

前言 本来壮志凌云的想都做完 发现我在做梦。。。 朱刘算法太难了(自己太懒发现性价比比较低之后就没做而且算法介绍也太难懂了好几个关键词含义都不给简直简直太难了我枯 HDU4081 Qin Shi Huang’s National Road System 题意:给你一个图的各个点的坐标 再给你每个点的权值…
暂无图片
编程学习 ·

Django开发

一.创建django项目二.新建应用 1. 建立应用python manage.py startapp 应用名2. 在[setting]->[INSTALLED_APPS]建立应用三. 建立数据库 1. 编写文章数据模型类2. 建立迁移文件 python manage.py makemigrations3. 生成数据库 python manage.py migrate四.建立超级管理员 p…
暂无图片
编程学习 ·

Python之闭包的学习

什么是闭包?内部函数对外部函数作用域内变量的引用,则内部函数称为闭包。闭包的条件:必须有内嵌函数(函数里面的函数)。内嵌函数必须引用一个定义在外部函数里面的变量。外部函数必须返回内嵌函数。 列子:def funcOut(a):def funcIn(b):return a + breturn funcInf = fun…
暂无图片
编程学习 ·

面试之一句话简述volatile

volatile是轻量级的synchronized,他保证了可见性,底层的关键主要是LOCK指令,该指令有两个作用,一是强制把处理器缓存写回内存,二是一旦处理器缓存写回了内存,就让其他处理器上相同的缓存失效,这样的话,其他处理器想要修改某个被写回内存的变量,就得重新去内存取值,而…
暂无图片
编程学习 ·

基于小程序请求接口 wx.request 封装的类 axios 请求

基于小程序请求接口 wx.request 封装的类 axios 请求Introductionwx.request 的配置、axios 的调用方式源码戳我 feature支持 wx.request 所有配置项支持 axios 调用方式支持 自定义 baseUrl支持 自定义响应状态码对应 resolve 或 reject 状态支持 对响应(resolve/reject)分别…
暂无图片
编程学习 ·

二进制与十进制转换工具类

package util;/*** 二进制工具类* * @author 谢辉* @time 2020.07.01**/ public class BinaryUtil {/*** 十进制数字转二进制* * @param num 十进制数字* @param strResult 结果容器,追加结果用,* @return 返回结果字符串*/public static String DecimalToBinary(Integ…