代码随想录算法训练营第四十一天|416. 分割等和子集

416. 分割等和子集 新思路

定义

dp[j]表示背包总容量是j,放进物品后,背包是否装满

递推公式

dp[j] = dp[j - nums[i]] || dp[j];
dp[j]是否装满取决于情况一或者情况二:
情况一:放入物品i,是否装满,即判断dp[j - nums[i]]是否已经满了
情况二:不放入物品i,是否装满,即判断dp[j]是否装满

初始化

dp[0] = true;
其余为false
当j==nums[i]时,dp[j - nums[i]]一定为装满
其余按照定义应该为未装满

遍历顺序

先物品,后倒序遍历背包
在这里插入图片描述

总结

在这里插入图片描述
在这里插入图片描述

最近更新

  1. TCP协议是安全的吗?

    2024-03-10 10:26:05       16 阅读
  2. 阿里云服务器执行yum,一直下载docker-ce-stable失败

    2024-03-10 10:26:05       16 阅读
  3. 【Python教程】压缩PDF文件大小

    2024-03-10 10:26:05       15 阅读
  4. 通过文章id递归查询所有评论(xml)

    2024-03-10 10:26:05       18 阅读

热门阅读

  1. nextjs上的DDD架构

    2024-03-10 10:26:05       21 阅读
  2. 分布式BASE理论

    2024-03-10 10:26:05       23 阅读
  3. AI辅助研发正在成为造福人类的新生科技力量

    2024-03-10 10:26:05       21 阅读
  4. 用cin和cout实现数据的输入输出——例题

    2024-03-10 10:26:05       19 阅读
  5. 我是如何写作的?

    2024-03-10 10:26:05       21 阅读
  6. vscode remote ssh 连接 ubuntu/linux报错解决方法

    2024-03-10 10:26:05       19 阅读