当前位置: 首页 > ds >正文

leetcode day36 01背包问题 494

494 目标和

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ,然后串联起所有整数,可以构造一个 表达式 :

  • 例如,nums = [2, 1] ,可以在 2 之前添加 '+' ,在 1 之前添加 '-' ,然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

  • 1 <= nums.length <= 20
  • 0 <= nums[i] <= 1000
  • 0 <= sum(nums[i]) <= 1000
  • -1000 <= target <= 1000

示例 1:

输入:nums = [1,1,1,1,1], target = 3
输出:5
解释:一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

示例 2:

输入:nums = [1], target = 1
输出:1

有点难想到用背包问题来解题,多练

二维初始化复杂一点

/*
加法为x,减法则为sum-x,target=x-(sum-x)
所以x=(target+sum)/2
考虑不满足的情况
(1)s+sum为奇数不满足
(2)abs(target)>sum也不满足
转化为01背包问题
1、dp[i][j]为物品[0,i]装满背包j的方法数
2、确定递推公式
(1)不放物品i,dp[i][j]=dp[i-1][j]
(2)放物品i,dp[i][j]=dp[i-1][j-nums[i]]
3、初始化 
(1)nums[i]不为0时
dp[0][0]=1//什么都不放为一种情况
dp[0][nums[0]]=1
dp[i][0]=1
(2)nums[i]为0时
如果nums[0]=0,那么dp[0][0]=2
如果nums[1]也等于=0,那么dp[0][0]=4
总结规律:nums[0,i]0的个数为cnt,那么dp[0][i]=2的cnt次方
*/
int Sum(int s[],int numsSize){int sum=0;for(int i=0;i<numsSize;i++)sum+=s[i];return sum;
}
int findTargetSumWays(int* nums, int numsSize, int target) {int dp[25][1005]={};int sum=Sum(nums,numsSize),cnt=0;if((sum+target)%2!=0||abs(target)>sum)return 0;int bag=(sum+target)/2;//背包容量dp[0][0]=1;//初始化第一行if(nums[0]<=bag)dp[0][nums[0]]=1;//初始化第一列for(int i=0;i<numsSize;i++){if(nums[i]==0)cnt++;dp[i][0]=pow(2,cnt);}for(int i=1;i<numsSize;i++){for(int j=0;j<=bag;j++){if(nums[i]>j)dp[i][j]=dp[i-1][j];//放不下不放else dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]];}}return dp[numsSize-1][bag];
}

一维dp数组

/*一维数组dp
dp[j]表示容量为j的背包能放入的最大价值
递推公式  dp[j]+=dp[j-nums[i]];
初始化 dp[0]=1
因为后面循环包括nums[i]=0的情况
*/
int findTargetSumWays(int* nums, int numsSize, int target) {int dp[1005]={};int sum=0;for(int i=0;i<numsSize;i++)sum+=nums[i];if((sum+target)%2!=0||abs(target)>sum)return 0;dp[0]=1;int bag=(target+sum)/2;for(int i=0;i<numsSize;i++){for(int j=bag;j>=nums[i];j--){dp[j]+=dp[j-nums[i]];}}return dp[bag];
}

1

http://www.xdnf.cn/news/1109.html

相关文章:

  • react 父子组件通信 子 直接到父, 父 forwardref子
  • 基于扣子(Coze.cn)与火山引擎构建高性能智能体的实践指南
  • 【Linux网络与网络编程】07.应用层协议HTTPS
  • LLM 论文精读(二)Training Compute-Optimal Large Language Models
  • Docker 数据卷
  • UML概览
  • Spark与Hadoop之间的联系和对比
  • 成熟软件项目解决方案:360°全景影像显控软件系统
  • .NET仓储层在 using 块中创建 SqlSugarClient 的风险
  • python兴趣匹配算法
  • <四级英语词汇> 2025.4.22
  • Cesium学习笔记——坐标系统及坐标转换
  • 文献×汽车 | 基于 ANSYS 的多级抛物线板簧系统分析
  • 【深度学习】#8 循环神经网络
  • 日常记录-logback脱敏
  • 【扫描件批量改名】批量识别扫描件PDF指定区域内容,用识别的内容修改PDF文件名,基于C++和腾讯OCR的实现方案,超详细
  • 4.22学习总结
  • Spring Web MVC入门
  • Apache SeaTunnel:新一代开源、高性能数据集成工具
  • 【2025最新Java面试八股】如何理解MySQL的MVCC机制?
  • 安宝特案例 | 某知名日系汽车制造厂,借助AR实现智慧化转型
  • Oracle--SQL性能优化与提升策略
  • 类加载器与jvm的内存
  • 数据库性能优化(sql优化)_分布式优化思路02_yxy
  • uniapp开发2--uniapp中的条件编译总结
  • 探索科技的边界:代理IP与汽车产业链的创新之旅
  • 使用 LlamaIndex Workflows 与 Elasticsearch
  • LeetCode 热题 100_分割等和子集(89_416_中等_C++)(动态规划)
  • 数据孤岛、技术断层、ROI迷雾:传统企业数字化转型的三大坑,如何破局?
  • JAVA设计模式——(二)组合模式