算法笔记|Day31动态规划IV

2024-08-22 11:52

本文主要是介绍算法笔记|Day31动态规划IV,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

算法笔记|Day31动态规划IV

  • ☆☆☆☆☆leetcode 1049.最后一块石头的重量II
    • 题目分析
    • 代码
  • ☆☆☆☆☆leetcode 494.目标和
    • 题目分析
    • 代码
  • ☆☆☆☆☆leetcode 474.一和零
    • 题目分析
    • 代码

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

题目链接:leetcode 1049.最后一块石头的重量II

题目分析

此题可以将stones分成两个总和最接近的两个部分,作差即为求得的最小值。若想使两部分最接近,第一部分的总和的目标应设置为target=sum/2,其中sum为集合中各个元素的和。这样可以得到的第一部分最大的总和为dp[target],第二部分的总和为sum-dp[target],差为(sum-dp[target])-dp[target]=sum-dp[target]*2。(注意点dp[target]总是小于target,而target小于等于sum/2)
1.dp数组含义:dp[j]表示总重量不超过j的几个数和的最大值(相当于0-1背包问题中的容量为j的背包最大的价值总和);
2.递推公式:dp[j]=Math.max(dp[j],dp[j-stones[i]]+stones[i])(相当于集合中每个元素的weight和value相同,都是数值stones);
3.初始化:dp[0]=0;
4.遍历顺序:先遍历stones嵌套遍历背包,背包一定是要倒序遍历。

代码

class Solution {public int lastStoneWeightII(int[] stones) {int sum=0;for(int stone:stones)sum+=stone;int target=sum/2;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-dp[target]*2;}
}

☆☆☆☆☆leetcode 494.目标和

题目链接:leetcode 494.目标和

题目分析

此题可以将nums分成两个两个部分,第一部分为+号,第二部分为-号。记第一部分的总和为left,第二部分的总和为right,注意点应该有left+right=sum①,left-right=target②,这样可以得到第一部分的和为left=(sum+target)/2。考虑若sum+target为奇数或者sum+target<0,则一定没有元素符合题意,返回0。
1.dp数组含义:dp[j]表示填满容量为j(包括j)背包的方法数量;
2.递推公式:dp[j]+=dp[j-nums[i]]
(以dp[j]其中j为5举例,要想填满容量为5的背包,要考虑以下情况:
已经有一个1(nums[i])的话,有dp[4]种方法凑成容量为5的背包。
已经有一个2(nums[i])的话,有dp[3]种方法凑成容量为5的背包。
已经有一个3(nums[i])的话,有dp[2]种方法凑成容量为5的背包
已经有一个4(nums[i])的话,有dp[1]种方法凑成容量为5的背包
已经有一个5(nums[i])的话,有dp[0]种方法凑成容量为5的背包
那么凑整dp[5]的总方法数也就是把所有的dp[j - nums[i]]累加起来);
3.初始化:dp[0]=1;(考虑把容量为0也当做一种方法,这样可以递推得到其他结果。若dp[0]是0,递推结果将都是0)
4.遍历顺序:先遍历数字嵌套遍历背包,背包一定是要倒序遍历。

代码

class Solution {public int findTargetSumWays(int[] nums, int target) {int sum=0;for(int num:nums)sum+=num;if((target+sum)%2==1||target+sum<0)return 0;int left=(target+sum)/2;int dp[]=new int[left+1];dp[0]=1;for(int i=0;i<nums.length;i++){for(int j=left;j>=nums[i];j--){dp[j]+=dp[j-nums[i]];}}return dp[left];}
}

☆☆☆☆☆leetcode 474.一和零

题目链接:leetcode 474.一和零

题目分析

此题可以视为一个装满0的容量为m、装满1的容量为n的背包,可以装多少个物品(也就是字符串),每个字符串的重量也就是字符串中0和1的数量,每个字符串的价值是1(加入个数即加一),相当于一个二维的背包。
1.dp数组含义:dp[i][j]表示最多有i个0和j个1的strs的最大子集的元素个数;
2.递推公式:dp[i][j]=Math.max(dp[i-x][j-y]+1,dp[i][j]);(其中x为当前字符串中0的个数,y为当前字符串中1的个数,x和y相当于物品的重量,物品的价值为1相当于计数);
3.初始化:dp[0][0]=0;
4.遍历顺序:先遍历物品(字符串)嵌套遍历背包,背包一定是要倒序遍历。

代码

class Solution {public int findMaxForm(String[] strs, int m, int n) {int dp[][]=new int[m+1][n+1];for(String str:strs){int x=0,y=0;for(char s:str.toCharArray()){if(s=='0')x++;elsey++;}for(int i=m;i>=x;i--){for(int j=n;j>=y;j--)dp[i][j]=Math.max(dp[i-x][j-y]+1,dp[i][j]);}}return dp[m][n];}
}

这篇关于算法笔记|Day31动态规划IV的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1096200

相关文章

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

基于Canvas的Html5多时区动态时钟实战代码

《基于Canvas的Html5多时区动态时钟实战代码》:本文主要介绍了如何使用Canvas在HTML5上实现一个多时区动态时钟的web展示,通过Canvas的API,可以绘制出6个不同城市的时钟,并且这些时钟可以动态转动,每个时钟上都会标注出对应的24小时制时间,详细内容请阅读本文,希望能对你有所帮助...

Vue中动态权限到按钮的完整实现方案详解

《Vue中动态权限到按钮的完整实现方案详解》这篇文章主要为大家详细介绍了Vue如何在现有方案的基础上加入对路由的增、删、改、查权限控制,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、数据库设计扩展1.1 修改路由表(routes)1.2 修改角色与路由权限表(role_routes)二、后端接口设计

前端 CSS 动态设置样式::class、:style 等技巧(推荐)

《前端CSS动态设置样式::class、:style等技巧(推荐)》:本文主要介绍了Vue.js中动态绑定类名和内联样式的两种方法:对象语法和数组语法,通过对象语法,可以根据条件动态切换类名或样式;通过数组语法,可以同时绑定多个类名或样式,此外,还可以结合计算属性来生成复杂的类名或样式对象,详细内容请阅读本文,希望能对你有所帮助...