leetcode 416. 分割等和子集

2023.8.12

         太难了ToT.... 一题做了一个下午。

        本题是动规题目的0-1背包问题系列。将分割子集转化为 在nums数组中任取任意元素使其和等于总元素和的一半,即可满足题目条件。

        1、使用一个bool型二维dp数组,dp[i][j] 的含义是:任取nums数组在索引小于等于i之前的元素,能否使其和等于target? (target为数组元素总和的一半)。

       2、 确定dp数组的含义之后,再进行初始化:首先是第0列的初始化:此时target=0,极端情况,此时可以不选取元素,和即为0,因此将这一列全置为true。  其次是第0行的初始化:此时能选取的元素只有nums[0],因此将target=nums[0]的地方置为true,其余的都置为false。

        3、最后就是遍历赋值。dp[i][j] 有两个来源:第一个是不选取新的元素,即dp[i][j] = dp[i-1][j] 第二个就是可以选取新的元素,也可以不选取,看哪个是true就选哪个,即dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]] ,dp[i-1][j-nums[i]]即为不选取,此时为什么是i-1呢?因为每个元素只能选取一次i对应的元素已经被选取了,只能在前i-1个元素中选取了。

        代码如下:

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(int i=0; i<nums.size(); i++)
        {
            sum += nums[i];
        }
        if(sum % 2 == 1) return false;
        int target = sum / 2; 
        vector<vector<bool>> dp(nums.size(),vector<bool>(target + 1));
        //初始化第一列
        for(int i=0; i<nums.size(); i++)
        {
            dp[i][0] = true;
        }
        //初始化第一行
        for(int i=1; i<=target; i++)
        {
            if(nums[0] == i) dp[0][i] = true;
        }
        for(int i=1; i<nums.size(); i++)
        {
            for(int j=1; j<=target; j++)
            {
                if(j < nums[i]) dp[i][j] = dp[i-1][j]; //此时容量容不下nums[i]这个数,所以不使用nums[i]。
                else dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]; //可以使用nums[i],也可以不使用。
                //此时为什么是i-1呢?因为每个元素只能选取一次,i对应的元素已经被选取了,只能在前i-1个元素中选取了。
            }
        }
        return dp[nums.size()-1][target];
    }
};

        附上我画的草稿图:

         紫色部分为初始化部分,蓝色部分为遍历赋值部分。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

已有公司将ChatGPT集成到客服中心以增强用户体验

Ozonetel正在利用ChatGPT来改善客户体验。该公司表示&#xff0c;他们通过使用ChatGPT收集与客户互动过程收集的“语料”能够更有针对性地提高服务效率&#xff0c;提供个性化的用户体验&#xff0c;并实现更高的客户满意度。[1] 通过这套解决方案&#xff0c;客服中心将拥有一…

27.Netty源码之FastThreadLocal

highlight: arduino-light FastThreadLocal FastThreadLocal 的实现与 ThreadLocal 非常类似&#xff0c;Netty 为 FastThreadLocal 量身打造了 FastThreadLocalThread 和 InternalThreadLocalMap 两个重要的类。下面我们看下这两个类是如何实现的。 FastThreadLocalThread 是对…

c++文件流详细笔记

c++流 IO :向设备输入数据和输出数据 C++的IO流 设备: 文件控制台特定的数据类型(stringstream)c++中,必须通过特定的已经定义好的类, 来处理IO(输入输出) 文件流 文件流: 对文件进行读写操作 头文件: 类库: ifstream 对文件输入(读文件) ofstream 对文件输出(写…

idea中如何处理飘红提示

idea中如何处理飘红提示 在写sql时&#xff0c;总是会提示各种错误 查找资料&#xff0c;大部分都是说关提示&#xff0c;这里把错误提示选择为None即可 关掉以后&#xff0c;也确实不显示任何提示了&#xff0c;但总有一种掩耳盗铃的感觉 这个sms表明明存在&#xff0c;但是还…

深度学习常用的python库学习笔记

文章目录 数据分析四剑客Numpyndarray数组和标量之间的运算基本的索引和切片数学和统计方法线性代数 PandasMatplotlibPIL 数据分析四剑客 Numpy Numpy中文网 ndarray 数组和标量之间的运算 基本的索引和切片 数学和统计方法 线性代数 Pandas Pandas中文网 Matplotlib Mat…

MuMu模拟器运行一段时间后Device.Present耗时突然上升

1&#xff09;MuMu模拟器运行一段时间后Device.Present耗时突然上升 2&#xff09;​如何在运行过程中获得温度信息 3&#xff09;Input System鼠标更换主按键的Bug 4&#xff09;如何禁止Unity向https://config.uca.cloud.unity3d.com发送设备信息 这是第347篇UWA技术知识分享…

Leetcode-每日一题【剑指 Offer 26. 树的子结构】

题目 输入两棵二叉树A和B&#xff0c;判断B是不是A的子结构。(约定空树不是任意一个树的子结构) B是A的子结构&#xff0c; 即 A中有出现和B相同的结构和节点值。 例如: 给定的树 A: 3 / \ 4 5 / \ 1 2 给定的树 B&#xff1a; 4 / 1 返回 true&#xff0…

C++笔记之静态成员函数的使用场景

C笔记之静态成员函数的使用场景 C静态成员函数的核心特点是不与特定类实例相关&#xff0c;可通过类名直接调用&#xff0c;用于执行与类相关的操作而无需创建类对象。其主要用途是在类级别上共享功能&#xff0c;管理全局状态或提供工具函数。 code review! 文章目录 C笔记之…

悬崖传感器调试问题总结

悬崖传感器原理 使用ADC采样电路&#xff0c;周期的进行开/关灯&#xff0c;获取ADC采样值。根据预先设置好ADC门限&#xff0c;判断是否为悬崖。ADC的精度是12位&#xff0c;对应电路的电压是3.3伏&#xff0c;悬崖传感器通过开灯和关灯&#xff0c;接收的不同灯光强度&#x…

[数据集][目标检测]道路坑洼目标检测数据集VOC格式1510张2类别

数据集格式&#xff1a;Pascal VOC格式(不包含分割路径的txt文件和yolo格式的txt文件&#xff0c;仅仅包含jpg图片和对应的xml) 图片数量(jpg文件个数)&#xff1a;1510 标注数量(xml文件个数)&#xff1a;1510 标注类别数&#xff1a;2 标注类别名称:["keng","…

Redis缓存设计

缓存能够有效地加速应用的读写速度&#xff0c;同时也可以降低后端负载&#xff0c;对日常应用的开发至关重要。但是将缓存加入应用架构后也会带来一些问题&#xff0c;本文将针对这些问题介绍缓存使用技巧和设计方案。 1缓存的收益和成本 下图左侧为客户端直接调用存储层的架…

vector【1】介绍与使用(超详解哦)

vector 引言vector介绍接口使用默认成员函数迭代器容量元素访问数据修改 总结 引言 在string部分&#xff0c;我们详细的介绍了各个接口的使用&#xff0c;虽然其不属于STL的一部分&#xff0c;但是接口与STL中的容器相似&#xff0c;所以我们在学习使用vector等STL容器的使用…

JavaScript之BOM+window对象+定时器+location,navigator,history对象

一.BOM概述 BOM即浏览器对象模型,它提供了独立于内容而与窗口进行交互的对象 BOM的顶级对象是window 二.window对象的常见事件 1.窗口加载事件window.onload window.onload function(){} 或者 window.addEventListener("onload" , function(){}); window.onlo…

websocket知识点

http协议 http协议特点&#xff1a; 无状态协议每个请求是独立的单双工通信&#xff0c;且服务器无法主动给客户端发信息http协议受浏览器同源策略影响 http实现双向通信方法: 轮询长轮询iframe流sse EventSource websocket协议 websocket协议: 全双工协议支持跨域支持多…

近地面无人机植被定量遥感与生理参数反演技术

遥感&#xff08;RS-Remote Sensing&#xff09;——不接触物体本身&#xff0c;用传感器收集目标物的电磁波信息&#xff0c;经处理、分析后&#xff0c;识别目标物&#xff0c;揭示其几何、物理性质和相互关系及其变化规律的现代科学技术。 换言之&#xff0c;即是“遥远的感…

【Ubuntu】简化反向代理和个性化标签页体验

本文将介绍如何使用Docker部署Nginx Proxy Manager和OneNav&#xff0c;两个功能强大且易用的工具。Nginx Proxy Manager用于简化和管理Nginx反向代理服务器的配置&#xff0c;而OneNav则提供个性化的新标签页体验和导航功能。通过本文的指导&#xff0c;您将学习如何安装和配置…

SQL-每日一题【1517. 查找拥有有效邮箱的用户】

题目 表: Users 编写一个解决方案&#xff0c;以查找具有有效电子邮件的用户。 一个有效的电子邮件具有前缀名称和域&#xff0c;其中&#xff1a; 前缀 名称是一个字符串&#xff0c;可以包含字母&#xff08;大写或小写&#xff09;&#xff0c;数字&#xff0c;下划线 _ &…

[保研/考研机试] KY163 素数判定 哈尔滨工业大学复试上机题 C++实现

题目链接&#xff1a; 素数判定https://www.nowcoder.com/share/jump/437195121691718831561 描述 给定一个数n&#xff0c;要求判断其是否为素数&#xff08;0,1&#xff0c;负数都是非素数&#xff09;。 输入描述&#xff1a; 测试数据有多组&#xff0c;每组输入一个数…

Vue3入门

1. 为什么要学 Vue3 &#xff1f; Vue3 的优势&#xff1a; Vue2 选项式 API vs Vue3 组合式API 2. create-vue搭建Vue3项目 2.1 认识 create-vue create-vue是Vue官方新的脚手架工具&#xff0c;底层切换到了 vite&#xff08;下一代构建工具&#xff09;&#xff0c;为开发…

【Vue3】keep-alive 缓存组件

当在 Vue.js 中使用 <keep-alive> 组件时&#xff0c;它将会缓存动态组件&#xff0c;而不是每次渲染都销毁和重新创建它们。这对于需要在组件间快速切换并且保持组件状态的情况非常有用。 <keep-alive> 只能包含&#xff08;或者说只能渲染&#xff09;一个子组件…