【代码随想录_Day30】1049. 最后一块石头的重量 II 494. 目标和 474.一和零

news/2024/9/23 11:17:51/

Day30 OK,今日份的打卡!第三十天

  • 以下是今日份的总结
    • 最后一块石头的重量 II
    • 目标和
    • 一和零

以下是今日份的总结

1049 最后一块石头的重量 II
494 目标和
474 一和零

今天的题目难度不低,掌握技巧了就会很简单,尽量还是写一些简洁代码 ^ _ ^

最后一块石头的重量 II

思路:

1.确定dp数组以及下标的含义
------ dp[j]表示容量(这里说容量更形象,其实就是重量)为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]都初始化为0就可以了
4.确定遍历顺序
------如果使用一维dp数组,物品遍历的for循环放在外层,遍历背包的for循环放在内层,且内层for循环倒序遍历!
5.举例推导dp数组

值得注意的是

最后dp[target]里是容量为target的背包所能背的最大重量。
在计算target的时候,target = sum / 2 因为是向下取整,所以sum - dp[target] 一定是大于等于dp[target]的。
那么相撞之后剩下的最小石头重量就是 (sum - dp[target]) - dp[target]。

//二维dp数组实现int lastStoneWeightII(vector<int>& stones) {vector<int>dp(15001,0);int sum = 0;//这堆石头的总重量for(int i = 0;i<stones.size();i++) sum += stones[i];int target = sum / 2;//遍历物品for(int i = 0;i < stones.size(); i++){//遍历背包for(int j = target ; j>=stones[i];j--){//不放石头和放石头 中 取最大值 dp[j] = max(dp[j],dp[j - stones[i]]+stones[i]);}       }return sum - dp[target] - dp[target];}

目标和

思路:
既然为target,那么就一定有
left - right = target
left + right = sum
left = (target + sum)/2 。
此时问题就转化为,装满容量为left的背包,有几种方法。

1.确定dp数组以及下标的含义
------ 填满j(包括j)这么大容积的包,有dp[j]种方法
_
2.确定递推公式
------dp[j] += dp[j - nums[i]],没弄明白什么意思,记住就可以了
_
3.dp数组如何初始化
------在初始化的时候dp[0] 一定要初始化为1
_
4.确定遍历顺序
------nums放在外循环,target在内循环,且内循环倒序
_
5.举例推导dp数组

值得注意的是

dp[j] += dp[j - nums[i]];

   int findTargetSumWays(vector<int>& nums, int target) {int sum = 0;for(int i = 0; i < nums.size();i++){sum += nums[i];}//没有方案if((target+sum)%2==1||abs(target)>sum)return 0;int bagSize = (target + sum)/2;vector<int>dp( bagSize + 1,0);dp[0] = 1;for(int i = 0;i<nums.size();i++){for(int j = bagSize;j>=nums[i];j--){dp[j] = dp[j] + dp[j-nums[i]];//求组合类问题的公式,都是类似这种}}return dp[bagSize];}

一和零

思路:
本题中strs 数组里的元素就是物品,每个物品都是一个!
而m 和 n相当于是一个背包,两个维度的背包

1.确定dp数组以及下标的含义
------ dp[i][j]:最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
2.确定递推公式
------01背包的递推公式为:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
------本题,strs里的字符串有x个0,y个1。
------所以递推公式:dp[i][j] = max(dp[i][j], dp[i - x][j - y] + 1);
------字符串的x和y相当于物品的重量(weight[i]),字符串本身的个数相当于物品的价值(value[i])
3.dp数组如何初始化
------01背包的dp数组初始化为0就可以。
------因为物品价值不会是负数,初始为0,保证递推的时候dp[i][j]不会被初始值覆盖。
4.确定遍历顺序
------一定是外层for循环遍历物品,内层for循环遍历背包容量且从后向前遍历!
5.举例推导dp数组

值得注意的是

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

    int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); // 初始化全为0for (string str : strs) {int x = 0, y = 0;for (char a : str) {if (a == '0')//统计当前string的‘0’的个数x++;if (a == '1')//统计当前string的‘1’的个数y++;}for (int i = m; i >= x; i--) {for (int j = n; j >= y; j--) {dp[i][j] = max(dp[i][j], dp[i - x][j - y] + 1);}}}return dp[m][n];}

写在最后

----OK,今日份的博客就写到这里,这一期的动态规划好难想,明天继续加油!!!
—还没看下期的题,但是我的栈还有一节没写;
–追不上时间进度了!!又欠了三天的(笑
-🈚️。


http://www.ppmy.cn/news/1475999.html

相关文章

【JavaEE】synchronized原理详解

本文使用的是JDK1.8 目录 引言 Java对象在JVM的结构 对象头 Mark Word Monitor Owner EntryList WaitSet 加锁过程 锁消除 偏向锁 偏向锁使用 重偏向 撤销偏向 轻量级锁 重量级锁 自旋优化 引言 对于synchronized原理讲解之前&#xff0c;我们需要知道Java对象…

【iOS】alloc、init和new原理

目录 前言alloc方法源码探索1. alloc方法&#xff1a;2. _objc_rootAlloc()方法&#xff1a;3. callAlloc()方法&#xff1a;4. 里面有个_objc_rootAllocWithZone()方法&#xff1a;5. _class_createInstance()方法&#xff1a;instanceSize()方法malloc_instance方法initInsta…

华为USG6000V防火墙安全策略用户认证

目录 一、实验拓扑图 二、要求 三、IP地址规划 四、实验配置 1&#x1f923;防火墙FW1web服务配置 2.网络配置 要求1&#xff1a;DMZ区内的服务器&#xff0c;办公区仅能在办公时间内(9:00-18:00)可以访问&#xff0c;生产区的设备全天可以访问 要求2&#xff1a;生产区不…

ThreadLocal有哪些应用场景?底层如何实现?

1.如何使用&#xff1f; public class ThreadLocalExample {private static final ThreadLocal<String> threadLocal new ThreadLocal<>();public static void main(String[] args) {Runnable task () -> {threadLocal.set("Hello from thread " …

厨电,被AI重构的下一个十年|产业特稿

智能化赋能下&#xff0c;厨房从闲人免进的油污重地&#xff0c;到会朋交友的社交空间。随着老板、方太等头部厨电厂商纷纷布局AI&#xff0c;厨电行业的数字化、智能化正逐渐改变了人们和烹饪之间的交互&#xff0c;重塑着厨房固有的属性、定位和职能。 作者|斗斗 编辑|皮爷…

MPS 后端

本文来自&#xff1a; https://pytorch.org/docs/stable/notes/mps.html https://pytorch.ac.cn/docs/stable/notes/mps.html MPS 后端 mps 设备支持 在使用 Metal 编程框架的 MacOS 设备上&#xff0c;进行高性能 GPU 训练。 它引入了新的设备&#xff0c;将机器学习计算图和…

GIT相关操作,推送本地分支到远程仓库流程记录学习

git流程 切换到源文件夹&#xff1a;cd 源文件夹克隆远程仓库&#xff1a;git clone [ssh]进入项目文件夹&#xff1a;cd .\project\查看本地分支&#xff1a;git branch获取远程仓库更新&#xff0c;使远程同步&#xff1a;git fetch查看所有分支&#xff08;包括远程分支&am…

python爬虫豆瓣电影TOP250

以下代码是一个简单的网络爬虫程序&#xff0c;用于从豆瓣电影 Top250 页面获取电影信息并保存到 CSV 文件中。以下是代码的一些主要步骤和功能&#xff1a; 导入模块&#xff1a;代码开始部分导入了 requests 和 etree 模块用于网络请求和数据解析。 get_html(start) 函数&am…