尧图网络 高端网站定制 · 原创设计
免费咨询热线
400-888-6620
免费获取方案
动态规划巧解数组等分问题
LeetCode416给你一个只包含正整数的非空数组nums。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。示例 1输入nums [1,5,11,5]输出true解释数组可以分割成 [1, 5, 5] 和 [11] 。示例 2输入nums [1,2,3,5]输出false解释数组不能分割成两个元素和相等的子集。思路分割为两个相等的字串要满足和为偶数而且只要有一部分能凑出一半另一部分就一定能凑出一半采用动态规划的决策树。Python解法class Solution: def canPartition(self, nums: List[int]) - bool: s sum(nums) if s % 2 ! 0: return False target s // 2 dp [False] * (target 1) dp[0] True for num in nums: dp_tmp dp.copy() for i in range(target 1): if dp[i] and i num target: dp_tmp[i num] True dp dp_tmp if dp[target] True: return True return dp[target]Java解法class Solution { public boolean canPartition(int[] nums) { int s 0; for(int num : nums){ s s num; } if(s % 2 ! 0)return false; int target s / 2; boolean[] dp new boolean[target 1]; dp[0] true; for(int num : nums){ boolean[] dp_tmp dp.clone(); for(int i 0; i target; i){ if(dp[i] i num target){ dp_tmp[i num] true; } } dp dp_tmp; if(dp[target] true)return true; } return dp[target]; } }C解法class Solution { public: bool canPartition(vectorint nums) { int s 0; for(int num : nums){ s s num; } if(s % 2 ! 0) return false; int target s / 2; vectorbool dp(target 1, false); dp[0] true; for(int num : nums){ vectorbool dpTmp dp; for(int i 0; i target; i){ if(dp[i] i num target){ dpTmp[i num] true; } } dp dpTmp; if(dp[target]) return true; } return dp[target]; } };代码过程举例样例一nums[1,5,11,5]target11初始 dp[T,F,F,F,F,F,F,F,F,F,F,F]第一轮 num1dp_tmp [T,F,F,F,F,F,F,F,F,F,F,F]i0dp [0]Ti11 → dp_tmp [1]Tdp 更新[T,T,F,F,F,F,F,F,F,F,F,F]第二轮 num5dp_tmp [T,T,F,F,F,F,F,F,F,F,F,F]i0dp [0]T → i55 → dp_tmp [5]Ti1dp [1]T → i56 → dp_tmp [6]Tdp 更新[T,T,F,F,F,T,T,F,F,F,F,F]第三轮 num11dp_tmp [T,T,F,F,F,T,T,F,F,F,F,F]i0dp [0]T → i1111 → dp_tmp [11]T dp [11]True直接 return True样例二nums [2,3,4,5] 总和 14target7 初始 dp [T,F,F,F,F,F,F,F]第一轮 num2dp_tmp [T,F,F,F,F,F,F,F]i0dp[0]T → i22 → dp_tmp[2]Tdp [T,F,T,F,F,F,F,F]第二轮 num3dp_tmp [T,F,T,F,F,F,F,F]i0 → 033 → Ti2 → 235 → Tdp [T,F,T,T,F,T,F,F]第三轮 num4dp_tmp [T,F,T,T,F,T,F,F]i0→4T i2→6T i3→7T dp [7]True直接返回 True 最终 dp[T,F,T,T,T,T,T,T]
RELATED

相关推荐

人工智能“AI+虚仿”创新实训室 以“三谱一库”为核构筑未来实训中心

人工智能“AI+虚仿”创新实训室 以“三谱一库”为核构筑未来实训中心

当人工智能产增速加速奔跑,产业腾飞呼唤高质量的人才供给,职业教育的实训体系正面临一场深刻重构。恒点推出的人工智能“AI虚仿”创新实训室,以“三谱一库”为智能内核,依托人工智能、具身智能和空间智能三大核心技术,…

📅 2026/9/5 14:44:45
JavaScript 实现企业微信消息自动发送的技术实践

JavaScript 实现企业微信消息自动发送的技术实践

在日常的研发与团队协作中,将关键的业务日志、部署结果、或是线上告警实时推送到企业微信中,是提升团队响应效率的重要手段。今天和大家分享一个通过轻量级 API 接口实现企业微信消息自动发送的技术实践。本方案不依赖复杂的官方多重验证,非常…

📅 2026/10/7 0:36:48
国产大模型哪家强?深度评测文心一言4.5、通义千问Qwen2.5、混元HunYuan、Kimi+GLM-4五大主力模型(附私有化部署避坑清单)

国产大模型哪家强?深度评测文心一言4.5、通义千问Qwen2.5、混元HunYuan、Kimi+GLM-4五大主力模型(附私有化部署避坑清单)

更多请点击: https://kaifayun.com 第一章:国产大模型哪家强?深度评测文心一言4.5、通义千问Qwen2.5、混元HunYuan、KimiGLM-4五大主力模型(附私有化部署避坑清单) 国产大模型已进入“实用主义”阶段,性能…

📅 2026/9/10 0:22:23
MORE NEWS

更多资讯

📰

Windows 11安装MySQL 8.0完整指南与常见问题解决

1. MySQL 8.0在Windows 11上的完整安装指南 作为数据库管理员,我经常需要在各种Windows系统上部署MySQL。最近在Windows 11上安装MySQL 8.0时,发现官方安装包虽然简单,但隐藏了不少坑点。本文将分享我从下载到配置的完整过程,包含…

📰

KaiwuDB分布式数据库安装部署与性能调优实战

1. 初识KaiwuDB:一款值得关注的新型数据库 第一次听说KaiwuDB是在一个技术社区的热门讨论帖里,当时几位资深DBA正在比较各种新型数据库的性能特点。作为一个长期使用传统关系型数据库的开发者,我对这类新兴产品总是保持着谨慎但开放的态度。经…

📰

CentOS 7下Docker Redis三主三从集群一键部署脚本与避坑

简介:针对 CentOS 7.x 环境下希望快速搭建容器化 Redis 集群的 Linux 运维人员与后端开发者,提供一套可传递参数后自动执行的 shell 部署方案,用于减少逐节点配置、容器编排和基础环境准备中的重复操作,适合实验环境验证及中小项目…

📰

E3-1231 v3+B85-D3H黑苹果OpenCore EFI配置与避坑

简介:面向 Intel E3 1231V3 处理器搭配 B85 D3H 主板的黑苹果 EFI 引导配置包,主要服务于希望在非苹果硬件上安装并运行 macOS 的进阶玩家与装机爱好者。内容围绕 Clover/OpenCore 类引导所需组件展开,包含 ACPI 补丁、驱动内核扩展、设备属性…

📰

工业控制系统深度解析:35 电机速度控制

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

📰

Qt飞机大战源码拆解:从工程结构到二次开发实战

简介:这份资源是面向Qt初学者与游戏开发入门者的「飞机大战」完整项目源码包,围绕Qt框架的图形渲染、事件驱动与资源管理等核心能力展开,可用于课程设计、练手项目或Qt技术学习参考。压缩包共223个文件,约6.21MB,以105…

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

读完文章,想聊聊您的网站?

告诉我们您的行业与需求,资深顾问一对一梳理方案与报价,全程免费。

📞 💬