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];
    }
}
相关文章
|
5月前
|
存储 监控 固态存储
商业实战使用DeepSeek-R1构建本地RAG系统的完整方案02-优雅草卓伊凡
商业实战使用DeepSeek-R1构建本地RAG系统的完整方案02-优雅草卓伊凡
191 20
商业实战使用DeepSeek-R1构建本地RAG系统的完整方案02-优雅草卓伊凡
|
12月前
|
前端开发 开发工具 git
如何清理 docker 磁盘空间+修改 Gitea 服务器的 Webhook 设置+前端一些好学好用的代码规范-git hook+husky + commitlint
如何清理 docker 磁盘空间+修改 Gitea 服务器的 Webhook 设置+前端一些好学好用的代码规范-git hook+husky + commitlint
192 5
|
12月前
|
JavaScript 前端开发 数据安全/隐私保护
前端技术分享:使用Vue.js构建响应式表单
【10月更文挑战第1天】前端技术分享:使用Vue.js构建响应式表单
|
SQL 安全 算法
网络安全与信息安全:构建数字世界的防线在数字化浪潮席卷全球的今天,网络安全与信息安全已成为维系社会秩序、保障个人隐私与企业机密的重要基石。本文旨在深入探讨网络安全漏洞的本质、加密技术的前沿进展以及提升安全意识的有效策略,为读者揭示数字时代下信息保护的核心要义。
本文聚焦网络安全与信息安全领域,详细剖析了网络安全漏洞的形成机理、常见类型及其潜在危害,强调了及时检测与修复的重要性。同时,文章系统介绍了对称加密、非对称加密及哈希算法等主流加密技术的原理、应用场景及优缺点,展现了加密技术在保障数据安全中的核心地位。此外,针对社会普遍存在的安全意识薄弱问题,提出了一系列切实可行的提升措施,如定期安全培训、强化密码管理、警惕钓鱼攻击等,旨在引导公众树立全面的网络安全观,共同构筑数字世界的安全防线。
|
12月前
|
搜索推荐 Java Go
深入了解基数排序算法
深入了解基数排序算法
136 4
|
存储 缓存 负载均衡
使用一致性哈希让数据均匀分布
使用一致性哈希让数据均匀分布
213 3
|
JavaScript
Vue3相关组件项目依赖依赖版本信息
这篇文章展示了一个Vue 3项目中使用的组件和库的依赖版本信息,包括`ant-design-vue`、`swiper`、`vue`、`vue-router`等,以及开发依赖如`vite`、`vue-tsc`、`eslint`等。
204 1
Vue3相关组件项目依赖依赖版本信息
|
小程序 前端开发 Java
携程技术分享:亿级流量的办公IM及开放平台技术实践
本文总结了携程办公IM这些年的发展历程及未来的演进方向,并着重从高可用、高性能和可扩展的角度,探讨开放式平台的技术实现及发展方向。
267 1
携程技术分享:亿级流量的办公IM及开放平台技术实践
|
12月前
|
机器学习/深度学习 人工智能 运维
怎么样把数据治理和人工智能结合起来?
将数据治理和人工智能结合起来,可以提高数据管理的效率和准确性,减少风险和成本。未来,随着人工智能技术的不断发展和应用,数据治理和人工智能的结合将会更加紧密,为企业和社会带来更多的机遇和挑战。
|
12月前
|
自然语言处理 Linux
ChatGPT高效提问—prompt常见用法
ChatGPT高效提问—prompt常见用法
198 1