代码随想录算法训练营第四十三天|1049. 最后一块石头的重量 II、494. 目标和、474.一和零

本文主要是介绍代码随想录算法训练营第四十三天|1049. 最后一块石头的重量 II、494. 目标和、474.一和零,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

思路:

本题其实就是尽量让石头分成重量相同的两堆,相撞之后剩下的石头最小,这样就化解成01背包问题了。

是不是感觉和昨天讲解的416. 分割等和子集 (opens new window)非常像了。

本题物品的重量为stones[i],物品的价值也为stones[i]。

对应着01背包里的物品重量weight[i]和 物品价值value[i]。

接下来进行动规五步曲

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]);

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]才不会初始值所覆盖。

4.确定遍历顺序

在动态规划:关于01背包问题,你该了解这些!(滚动数组) (opens new window)中就已经说明:如果使用一维dp数组,物品遍历的for循环放在外层,遍历背包的for循环放在内层,且内层for循环倒序遍历!

5.举例推导dp数组

举例,输入:[2,4,1,1],此时target = (2 + 4 + 1 + 1)/2 = 4 ,dp数组状态图如下:

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

最后dp[target]里是容量为target的背包所能背的最大重量。

那么分成两堆石头,一堆石头的总重量是dp[target],另一堆就是sum - dp[target]。

在计算target的时候,target = sum / 2 因为是向下取整,所以sum - dp[target] 一定是大于等于dp[target]的

那么相撞之后剩下的最小石头重量就是 (sum - dp[target]) - dp[target]。

代码:

一维DP版

class Solution:def lastStoneWeightII(self, stones: List[int]) -> int:  total_sum = sum(stones)target = total_sum // 2dp = [0] * 15001 # dp = [0] * (target + 1) 也可以for stone in stones:  # 遍历物品for j in range(target, stone - 1, -1):  # 遍历背包dp[j] = max(dp[j], dp[j - stone] + stone)return total_sum - dp[target] - dp[target]
  • 时间复杂度:O(m × n) , m是石头总重量(准确的说是总重量的一半),n为石头块数
  • 空间复杂度:O(m)

494. 目标和

思路:

建议不懂的同学自己先用二维数组来做,比较好理解,理解了之后再用一维数组。
1. 含义:dp【i】【j】:从下标为【0...i】的物品里任取,填满j这么⼤容积的包,有dp【i】【j】种⽅法
2. 递推式:dp【i】【j】 = dp【i-1】【j】 + dp【i-1】[j-nums【i】]
dp【i-1】【j】是不将物品i放入背包的方式数,dp【i-1】[j-nums【i】]是将物品i放入背包的方式数
3. 初始化:dp【0】【0】 = 1 表示装满容量为0的背包,有1种⽅法,就是装0件物品。
如果nums【0】在范围内的话,dp【0】[nums【0】] = 1
其他全为0
4. 计算顺序:顺序,行优先

5.举例推导dp数组

代码:

二维dp数组

class Solution:def findTargetSumWays(self, nums: List[int], target: int) -> int:total_sum = sum(nums)  # 计算nums的总和if abs(target) > total_sum:return 0  # 此时没有方案if (target + total_sum) % 2 == 1:return 0  # 此时没有方案target_sum = (target + total_sum) // 2  # 目标和# 创建二维动态规划数组,行表示选取的元素数量,列表示背包容积dp = [[0] * (target_sum + 1) for _ in range(len(nums))]# 初始化第一行dp[0][0] = 1for j in range(target_sum + 1):if j==nums[0]:dp[0][j]=1# 初始化第一列# 当从nums数组的索引0到i的部分有n个0时(n > 0),每个0可以取+/-,因此有2的n次方中可以取到j = 0的方案# n = 0说明当前遍历到的数组部分没有0全为正数,因此只有一种方案可以取到j = 0(就是所有数都不取)num_zeros = 0for i in range(len(nums)):  if nums[i] == 0:  num_zeros += 1  dp[i][0] = 2 ** num_zeros# 动态规划过程for i in range(1, len(nums)):for j in range(1, target_sum + 1):if j < nums[i]:dp[i][j] = dp[i-1][j]else:dp[i][j] = dp[i-1][j] + dp[i - 1][j - nums[i]]return dp[len(nums)-1][target_sum]  # 返回达到目标和的方案数
  • 时间复杂度:O(n × m),n为正数个数,m为背包容量
  • 空间复杂度:O(n × m)

一维dp数组

class Solution:def findTargetSumWays(self, nums: List[int], target: int) -> int:total_sum = sum(nums)  # 计算nums的总和if abs(target) > total_sum:return 0  # 此时没有方案if (target + total_sum) % 2 == 1:return 0  # 此时没有方案target_sum = (target + total_sum) // 2  # 目标和dp = [0] * (target_sum + 1)  # 创建动态规划数组,初始化为0dp[0] = 1  # 当目标和为0时,只有一种方案,即什么都不选for num in nums:for j in range(target_sum, num - 1, -1):dp[j] += dp[j - num]  # 状态转移方程,累加不同选择方式的数量return dp[target_sum]  # 返回达到目标和的方案数
  • 时间复杂度:O(n × m),n为正数个数,m为背包容量
  • 空间复杂度:O(m)

474. 一和零

思路:

本题中strs 数组里的元素就是物品,每个物品都是一个!

而m 和 n相当于是一个背包,两个维度的背包

理解成多重背包的同学主要是把m和n混淆为物品了,感觉这是不同数量的物品,所以以为是多重背包。

但本题其实是01背包问题!

只不过这个背包有两个维度,一个是m 一个是n,而不同长度的字符串就是不同大小的待装物品。

开始动规五部曲

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

dp[i][j]:最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。(容量为i,j的背包,最多能装dp[i][j]个物品)

2.确定递推公式

dp[i][j] 可以由前一个strs里的字符串推导出来,strs里的字符串有zeroNum个0,oneNum个1。

dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。

然后我们在遍历的过程中,取dp[i][j]的最大值。

所以递推公式:dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);

此时大家可以回想一下01背包的递推公式:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

对比一下就会发现,字符串的zeroNum和oneNum相当于物品的重量(weight[i]),字符串本身的个数相当于物品的价值(value[i])。

这就是一个典型的01背包! 只不过物品的重量有了两个维度而已。

3.dp数组如何初始化

在动态规划:关于01背包问题,你该了解这些!(滚动数组) (opens new window)中已经讲解了,01背包的dp数组初始化为0就可以。

因为物品价值不会是负数,初始为0,保证递推的时候dp[i][j]不会被初始值覆盖。(保证初始值不会影响递推公式的运算)

4.确定遍历顺序

在动态规划:关于01背包问题,你该了解这些!(滚动数组) (opens new window)中,我们讲到了01背包为什么一定是外层for循环遍历物品,内层for循环遍历背包容量且从后向前遍历!

那么本题也是,物品就是strs里的字符串,背包容量就是题目描述中的m和n。

有同学可能想,那个遍历背包容量的两层for循环先后循序有没有什么讲究?

没讲究,都是物品重量的一个维度,先遍历哪个都行!

5.举例推导dp数组

以输入:["10","0001","111001","1","0"],m = 3,n = 3为例

最后dp数组的状态如下所示:

474.一和零

代码:

class Solution:def findMaxForm(self, strs: List[str], m: int, n: int) -> int:dp = [[0] * (n + 1) for _ in range(m + 1)]  # 创建二维动态规划数组,初始化为0for s in strs:  # 遍历物品zeroNum = s.count('0')  # 统计0的个数oneNum = len(s) - zeroNum  # 统计1的个数for i in range(m, zeroNum - 1, -1):  # 遍历背包容量且从后向前遍历for j in range(n, oneNum - 1, -1):dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1)  # 状态转移方程return dp[m][n]
  • 时间复杂度: O(kmn),k 为strs的长度
  • 空间复杂度: O(mn)

这篇关于代码随想录算法训练营第四十三天|1049. 最后一块石头的重量 II、494. 目标和、474.一和零的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/971093

相关文章

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

Java中调用数据库存储过程的示例代码

《Java中调用数据库存储过程的示例代码》本文介绍Java通过JDBC调用数据库存储过程的方法,涵盖参数类型、执行步骤及数据库差异,需注意异常处理与资源管理,以优化性能并实现复杂业务逻辑,感兴趣的朋友... 目录一、存储过程概述二、Java调用存储过程的基本javascript步骤三、Java调用存储过程示

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性:

MySQL数据库的内嵌函数和联合查询实例代码

《MySQL数据库的内嵌函数和联合查询实例代码》联合查询是一种将多个查询结果组合在一起的方法,通常使用UNION、UNIONALL、INTERSECT和EXCEPT关键字,下面:本文主要介绍MyS... 目录一.数据库的内嵌函数1.1聚合函数COUNT([DISTINCT] expr)SUM([DISTIN

Java实现自定义table宽高的示例代码

《Java实现自定义table宽高的示例代码》在桌面应用、管理系统乃至报表工具中,表格(JTable)作为最常用的数据展示组件,不仅承载对数据的增删改查,还需要配合布局与视觉需求,而JavaSwing... 目录一、项目背景详细介绍二、项目需求详细介绍三、相关技术详细介绍四、实现思路详细介绍五、完整实现代码

Go语言代码格式化的技巧分享

《Go语言代码格式化的技巧分享》在Go语言的开发过程中,代码格式化是一个看似细微却至关重要的环节,良好的代码格式化不仅能提升代码的可读性,还能促进团队协作,减少因代码风格差异引发的问题,Go在代码格式... 目录一、Go 语言代码格式化的重要性二、Go 语言代码格式化工具:gofmt 与 go fmt(一)

HTML5实现的移动端购物车自动结算功能示例代码

《HTML5实现的移动端购物车自动结算功能示例代码》本文介绍HTML5实现移动端购物车自动结算,通过WebStorage、事件监听、DOM操作等技术,确保实时更新与数据同步,优化性能及无障碍性,提升用... 目录1. 移动端购物车自动结算概述2. 数据存储与状态保存机制2.1 浏览器端的数据存储方式2.1.

基于 HTML5 Canvas 实现图片旋转与下载功能(完整代码展示)

《基于HTML5Canvas实现图片旋转与下载功能(完整代码展示)》本文将深入剖析一段基于HTML5Canvas的代码,该代码实现了图片的旋转(90度和180度)以及旋转后图片的下载... 目录一、引言二、html 结构分析三、css 样式分析四、JavaScript 功能实现一、引言在 Web 开发中,

Python如何去除图片干扰代码示例

《Python如何去除图片干扰代码示例》图片降噪是一个广泛应用于图像处理的技术,可以提高图像质量和相关应用的效果,:本文主要介绍Python如何去除图片干扰的相关资料,文中通过代码介绍的非常详细,... 目录一、噪声去除1. 高斯噪声(像素值正态分布扰动)2. 椒盐噪声(随机黑白像素点)3. 复杂噪声(如伪

Java Spring ApplicationEvent 代码示例解析

《JavaSpringApplicationEvent代码示例解析》本文解析了Spring事件机制,涵盖核心概念(发布-订阅/观察者模式)、代码实现(事件定义、发布、监听)及高级应用(异步处理、... 目录一、Spring 事件机制核心概念1. 事件驱动架构模型2. 核心组件二、代码示例解析1. 事件定义