10_最后一块石头的重量

简介: 10_最后一块石头的重量

1049.最后一块石头的重量II

题目难度:中等

有一堆石头,每块石头的重量都是正整数。

每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <= y。那么粉碎的可能结果如下:

如果 x == y,那么两块石头都会被完全粉碎;

如果 x != y,那么重量为 x 的石头将会完全粉碎,而重量为 y 的石头新重量为 y-x。

最后,最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下,就返回 0。

示例:

  • 输入:[2,7,4,1,8,1]
  • 输出:1

解释:

  • 组合 2 和 4,得到 2,所以数组转化为 [2,7,1,8,1],
  • 组合 7 和 8,得到 1,所以数组转化为 [2,1,1,1],
  • 组合 2 和 1,得到 1,所以数组转化为 [1,1,1],
  • 组合 1 和 1,得到 0,所以数组转化为 [1],这就是最优值。

提示:

  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 1000

【思路】

动规五步曲:

  1. 确定dp数组以及下标的含义

dp[j]表示容量(这里说容量更形象,其实就是重量)为j的背包,最多可以背最大重量为dp[j]。

可以回忆一下01背包中,dp[j]的含义,容量为j的背包,最多可以装的价值为 dp[j]。

相对于 01背包,本题中,石头的重量是 stones[i],石头的价值也是 stones[i] ,可以 “最多可以装的价值为 dp[j]” == “最多可以背的重量为dp[j]”

2、确定递推公式

01背包的递推公式为:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

本题则是:dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);

一些同学可能看到这dp[j - stones[i]] + stones[i]中 又有- stones[i] 又有+stones[i],看着有点晕乎。

大家可以再去看 dp[j]的含义。

3、dp数组如何初始化

既然 dp[j]中的j表示容量,那么最大容量(重量)是多少呢,就是所有石头的重量和。

因为提示中给出1 <= stones.length <= 30,1 <= stones[i] <= 1000,所以最大重量就是30 * 1000 。

而我们要求的target其实只是最大重量的一半,所以dp数组开到15000大小就可以了。

当然也可以把石头遍历一遍,计算出石头总重量 然后除2,得到dp数组的大小。

我这里就直接用15000了。

接下来就是如何初始化dp[j]呢,因为重量都不会是负数,所以dp[j]都初始化为0就可以了,这样在递归公式dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);中dp[j]才不会初始值所覆盖。

int[] dp = new int[15001];

4、确定遍历顺序

如果使用一维dp数组,物品遍历的for循环放在外层,遍历背包的for循环放在内层,且内层for循环倒序遍历!

for (int i = 0; i < stones.size; i++) {
  for (int j = target; j >= stones[i]; j--) {
        dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
    }
}

5、打印dp数组

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int i : stones) {
            sum += i;
        }
        int target = sum >> 1;
        //初始化dp数组
        int[] dp = new int[target + 1];
        for (int i = 0; i < stones.length; i++) {
            //采用倒序
            for (int j = target; j >= stones[i]; j--) {
                //两种情况,要么放,要么不放
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return sum - 2 * dp[target];
    }
}
相关文章
|
9月前
|
安全 Java 数据挖掘
高效转换Word表格为Excel:Python方案全解析
本文介绍如何用Python自动化将Word表格转为Excel,解决手动复制易出错、耗时长等问题。基于python-docx读取表格,结合openpyxl或pandas写入,支持多表合并、数字格式识别、合并单元格处理及大文件优化,30行代码即可实现高效精准转换。(239字)
1041 13
|
9月前
|
机器学习/深度学习 人工智能 自然语言处理
解决垂直领域“幻觉”难题:智能客服机器人知识库构建与微调策略深度解析
大模型在客服场景的落地常受困于幻觉问题。合力亿捷通过悦问大模型知识库与 MPaaS 平台,深度融合 RAG 技术与可视化业务流程编排,从知识治理与白盒化管理双重维度构建确定性。这种培养型交付方法论有效解决了垂直领域应答不准的痛点,使 AI 真正进化为高准确率的数字员工。
548 1
|
10月前
|
存储 弹性计算 关系型数据库
阿里云中小企业扶持权益中心内容说明及节省上云操作手册参考
本文将以技术视角,结合最新权益细则,用通俗语言全面拆解权益中心的核心内容、适用场景、申请步骤和实操技巧,还整理了不同规模企业的高性价比组合方案,帮助你避开误区,用合理成本实现稳定上云。全文无营销话术,所有内容基于实测体验和官方规则整理,可直接作为上云操作手册参考。
658 1
|
10月前
|
存储 JSON 自然语言处理
十一年实战沉淀:淘宝商品评论数据深度解析与落地技巧
深耕淘宝评论分析11年,亲历数据结构迭代与解析挑战。本文详解评论数据核心字段、解析难点及破局技巧,分享实战验证的标准化流程,涵盖字符处理、动态规则、高效存储等关键环节,助力精准情感分析与用户洞察。
1040 1
|
10月前
|
人工智能 JSON API
AI说话为啥这么挑剔?对话格式的神秘力量
你有没有发现,同样一句'你好',有时候AI能正常聊天,有时候却写起了小说?这其实和AI的'暗号系统'有关。就像你点外卖需要告诉店家你的地址一样,和AI聊天也需要用对'格式'。掌握了这个秘密,你就能让本地部署的AI模型乖乖听话,不再胡言乱语! #人工智能 #模型部署 #对话系统 #技术原理"
921 7
|
10月前
|
存储 弹性计算 Linux
2026阿里云服务器新手选购与操作全指南
在数字化业务部署中,云服务器凭借弹性扩展、成本可控的优势,成为个人开发者和企业搭建网站、运行应用的核心选择。阿里云 ECS(弹性计算服务)作为国内主流云服务产品,地域节点丰富、配置灵活,但新手常因不熟悉购买路径与参数选择感到困惑。下面从购买前准备、核心购买方式、配置选择要点到控制台基础操作,梳理新手所需的全流程知识,助力高效完成上云部署。
|
10月前
|
存储 SQL 关系型数据库
云数据库多少钱?2026年阿里云数据库 RDS 收费标准:MySQL、SQL Server 等引擎价格解析
阿里云数据库 RDS(Relational Database Service)是全托管关系型数据库服务,支持 MySQL、SQL Server、PostgreSQL 和 MariaDB 四种主流引擎,适配从轻量测试到企业核心业务的不同需求。很多用户会被不同引擎、规格、计费方式的价格差异弄混淆,下面结合最新收费信息,用通俗语言梳理各引擎价格、影响因素及选型建议,帮大家精准把控成本。
|
10月前
|
人工智能 自动驾驶 搜索推荐
深度|AI浪潮已至:在2026年,我们真正需要掌握什么?
2026年,AI同事能力每7个月翻倍,职场迎来重塑。成功关键不再是知识量,而是与AI共舞的能力。从医疗到科研,AI成为无处不在的协作伙伴,但“工作废料”、信息泛滥与能源悖论也带来挑战。未来属于掌握人机协作的人:兼具批判思维、人性化技能与持续进化力。人类价值,在于让技术闪耀人性光芒。
746 1
|
10月前
|
人工智能 自然语言处理 搜索推荐
2026AI数字人技术、场景双驱动技术指导
AI数字人融合人工智能、3D渲染、语音合成等技术,具备类人外观与交互能力,广泛应用于客服、教育、医疗、娱乐等领域。依托大模型与多模态技术,正迈向个性化、轻量化与元宇宙融合,推动产业数字化升级。