Day43 动态规划 part05

Day43 动态规划 part05

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

我的思路:
提示说和划分两个和相等的子集差不多,猛然想到,这道题不就是划分子集,用sum - 和最大*2
代码就是划分和相同的子集的变形

解答:

class Solution {public int lastStoneWeightII(int[] stones) {int sum = Arrays.stream(stones).sum();int target = sum / 2;int[] dp = new int[target + 1];for(int i = 0; i < stones.length; i++) {for(int j = dp.length - 1; j >= stones[i]; j--) {dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);}}return sum - dp[target] * 2;}
}

494.目标和

我的思路:
经历了这些个题之后,我发现我要的都是dp[target],要么取值,要么计算,要么判断
这个target决定了背包dp的容量–dp[target + 1]
这道题又出现了dp[j] = dp[j - nums[i]] + xxx

上面其实可以总结为,一维背包问题,其中 dp[j] = dp[i] + dp[j - nums[i]]就是状态转移方程

chatGPT老大哥说
G哥太牛了

解答:

class Solution {public int findTargetSumWays(int[] nums, int target) {int sum = Arrays.stream(nums).sum();if(Math.abs(target) > sum) {return 0;}if((sum + target) % 2 == 1) {return 0;}int mytarget = (sum + target) / 2;int[] dp = new int[mytarget + 1];dp[0] = 1;for(int i = 0; i < nums.length; i++) {for(int j = dp.length - 1; j >= nums[i]; j--) {dp[j] += dp[j - nums[i]];}}return dp[mytarget];}
}

474.一和零

我的思路:
有1和0,是个二维背包问题
这个状态转移方程是dp[i][j] = Math.max(dp[i][j], dp[i - zeroCount][j - oneCount] + 1),而且是在for循环里面更新

解答:

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

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Cache多核之间的一致性MESI

快速链接: 【精选】ARMv8/ARMv9架构入门到精通-[目录] &#x1f448;&#x1f448;&#x1f448; 思考: 1、为什么要学习MESI协议&#xff1f; 哪里用到了&#xff1f;你确定真的用到了&#xff1f; 2、MESI只是一个协议&#xff0c;总得依赖一个硬件去执行该协议吧&#xff0c…

蓝桥杯 --- 日期问题模板

目录 1.如何判断闰年 2.如何遍历当前年份的每一天 3.如果想要输出某一年某一天到某一年某一天之间一共有多少天。 4.精确到具体周几到周几的问题分析 5.如何直接通过一层for循环枚举年月日 习题&#xff1a; 蓝桥杯竞赛特别喜欢考日期问题&#xff0c;今天给大家分享一下…

VMware虚拟机安装Linux教程

以管理员身份运行VMware 按一下win键不然显示不全 重启即可。

什么是智慧公厕?智慧旅游下的智慧公厕功能和特点

智慧旅游下的智慧公厕功能和特点&#xff1f;智慧旅游是景区、公园、游乐场、文化场馆等领域的一种信息化解决方案&#xff0c;智慧公厕是智慧旅游极为重要的一部分&#xff0c;能大大提升游客满意度。智慧公厕采用物联网、互联网、大数据、云计算等技术&#xff0c;实现旅游景…

【Spring实战项目】SpringBoot3整合WebSocket+拦截器实现登录验证!从原理到实战

&#x1f389;&#x1f389;欢迎光临&#xff0c;终于等到你啦&#x1f389;&#x1f389; &#x1f3c5;我是苏泽&#xff0c;一位对技术充满热情的探索者和分享者。&#x1f680;&#x1f680; &#x1f31f;持续更新的专栏《Spring 狂野之旅&#xff1a;从入门到入魔》 &a…

picGo图床搭建gitee和smms(建议使用)

picGoGitee 这个需要下载gitee插件, 因为官方频繁的检索文件类型, 有时候也会失效 如果没有特殊要求平时存个学习的要看图中文字的重要的图片建议就是smms, 免费也够用! 图片存本地不方便, 各种APP中来回传还会失帧损失画质, 所以你值得往下看 picGosmms 建议使用这个, sm…

Linux gcc day3

find命令&#xff08;importance&#xff09;&#xff1a; 语法&#xff1a;find pathname -options find /root -name test.c which命令&#xff1a; which [指令] 只搜索指令&#xff0c;在什么位置下 为什么文件夹带有颜色呢&#xff1f; 科普补充alias命令&#xff1a; ali…

银行数字化转型导师坚鹏:银行数字化转型给分行带来的8大价值

银行数字化转型给分行带来的8大价值 银行数字化转型对不仅对总行产生了深远影响、给总行带来了新质生产力&#xff0c;对分行也会产生重要价值&#xff0c;银行数字化转型导师坚鹏从以下8个方面进行详细分析&#xff0c;相信能够给您带来重要启发&#xff0c;从而加速银行分行…

精读 Generating Mammography Reports from Multi-view Mammograms with BERT

精读&#xff08;非常推荐&#xff09; Generating Mammography Reports from Multi-view Mammograms with BERT&#xff08;上&#xff09; 这里的作者有个叫 Ilya 的吓坏我了 1. Abstract Writing mammography reports can be errorprone and time-consuming for radiolog…

clickhouse 源码编译部署

clickhouse 源码编译部署 版本 21.7.9.7 点击build project&#xff0c;编译工程&#xff0c;经过一定时间&#xff08;第一次编译可能几个小时&#xff0c;后续再编译&#xff0c;只编译有改动的文件&#xff09;生成release目录 在cmake-build-release → programs目录下…

Java集合(个人整理笔记)

目录 1. 常见的集合有哪些&#xff1f; 2. 线程安全的集合有哪些&#xff1f;线程不安全的呢&#xff1f; 3. Arraylist与 LinkedList 异同点&#xff1f; 4. ArrayList 与 Vector 区别&#xff1f; 5. Array 和 ArrayList 有什么区别&#xff1f;什么时候该应 Array而不是…

STM32L4R9 的 QuadSPI Flash 通讯速率不理想

1. 引言 客户反应 STM32L4R9 同 QSPI Flash 通讯&#xff0c;测出来的读取速率为 10MB/s&#xff0c; 和理论值相差较大。 2. 问题分析 按照客户的时钟配置和 STM32L4R9 的数据手册中的数据&#xff0c;OSPI 读数速率为 10MB/s 肯定存在问题。同时我们也可以在 AN4760 应用手…

c++20协程详解(三)

前言 前面两节我们已经能够实现一个可用的协程框架了。但我们一定还想更深入的了解协程&#xff0c;于是我们就想尝试下能不能co_await一个协程。下面会涉及到部分模板编程的知识&#xff0c;主要包括&#xff08;模板偏特化&#xff0c;模板参数列表传值&#xff0c;模板函数…

理论实践-CPU性能监控工具-uptime-mpstat-pidstat-vmstat-top-ps-perf

CPU 性能工具。 首先&#xff0c;平均负载的案例。我们先用 uptime&#xff0c; 查看了系统的平均负载&#xff1b;而在平均负载升高后&#xff0c;又用 mpstat 和 pidstat &#xff0c;分别观察了每个 CPU 和每个进程 CPU 的使用情况&#xff0c;进而找出了导致平均负载升高的…

risc-v向量扩展strlen方法学习

riscv向量文档中给出了strlen的实现&#xff0c; 大概是这么一个思路&#xff0c; 加载向量: 使用向量加载指令&#xff08;如 vload&#xff09;从内存中加载一个向量长度的字符。比较向量与零: 使用向量比较指令&#xff08;如 vmask 或 vcmpeq&#xff09;来检查向量中的每…

【Spring篇】Spring IoC DI

个人主页&#xff1a;兜里有颗棉花糖 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【Spring系列】 本专栏旨在分享学习Spring MVC的一点学习心得&#xff0c;欢迎大家在评论区交流讨论&#x1f48c; 目录 前言一、IoC二、…

HTMLCSSJS

HTML基本结构 <html><head><title>标题</title></head><body>页面内容</body> </html> html是一棵DOM树, html是根标签, head和body是兄弟标签, body包括内容相关, head包含对内容的编写相关, title 与标题有关.类似html这种…

STM32-05基于HAL库(CubeMX+MDK+Proteus)串行通信案例(中断方式接收命令)

文章目录 一、功能需求分析二、Proteus绘制电路原理图三、STMCubeMX 配置引脚及模式&#xff0c;生成代码四、MDK打开生成项目&#xff0c;编写HAL库的功能代码五、运行仿真程序&#xff0c;调试代码 一、功能需求分析 在中断机制实现按键检测的案例之后&#xff0c;我们介绍串…

Flink运行机制相关概念介绍

Flink运行机制相关概念介绍 1. 流式计算和批处理2. 流式计算的状态与容错3. Flink简介及其在业务系统中的位置4. Flink模型5. Flink的架构6. Flink的重要概念7. Flink的状态、状态分区、状态缩放&#xff08;rescale&#xff09;和Key Group8. Flink数据交换9. 时间语义10. 水位…

sky06笔记下

1.边沿检测 检测输入信号din的上升沿&#xff0c;并输出pulse module edge_check ( clk, rstn, din, pulse ); input wire clk,rstn; input wire din; output reg pulse;wire din_dly;always (posedge clk or negedge rstn)beginif(!rstn)din_dly < 1b0;elsedin_dly < d…