算法萌新如何学好动态规划（3）( 六 )
个 ， 问是否存在一种选取方案 ， 使其满足某种条件 。 或者是否存在一种选取方案 ， 使其满足某种条件的同时 ， 得到某种参数的最值 。
这样归纳可能还是过于抽象 ， 因此我们将在下文「习题练习」中讲解一些具体的题型来帮助大家理解 。
文章插图
习题练习416. 分割等和子集题目描述给定一个只包含正整数的非空数组 。 是否可以将这个数组分割成两个子集 ， 使得两个子集的元素和相等 。
示例 1输入: [1, 5, 11, 5]输出: true解释: 数组可以分割成 [1, 5, 5] 和 [11].?示例 2输入: [1, 2, 3, 5]输出: false解释: 数组不能分割成两个元素和相等的子集.提示
- 每个数组中的元素不会超过 100
- 数组的大小不会超过 200
进行这一步转换之后 ， 则可以较为明显的看出该问题本质上是从 N 物品中选取若干个物品 ， 即「背包问题」 。 并且每个物品只能选一次 ， 因此是「0/1 背包」模型 。
仿照「0/1 背包」模型 ， 我们可以定义
文章插图为仅考虑前 i 个物品 ， 是否存在一种选择方案使其数值和为 j 。 我们规定若
文章插图则表示存在一种方案；若
文章插图则表示不存在可行方案 。
因此我们可以得到如下「DP 转移方程」：
文章插图定义一下初始条件 ，
文章插图。 接下来直接套用「0/1 背包」滚动数组版本的代码即可完成本题 ， 具体细节见下述代码 。
C++ 代码实现
class Solution {public:vector f;bool canPartition(vectorfor(int item:nums) sum += item;if(sum % 2 != 0) return 0;sum /= 2;// 开辟存储空间f.resize(sum+1);f[0] = 1;// DP 过程for(int i = 1; i <= nums.size(); i++)for(int j = sum; j >= nums[i-1]; j--)if(f[j-nums[i-1]] == 1)f[j] = 1;if(f[sum]) return 1;else return 0;}}; 494. 目标和?题目描述给定一个非负整数数组 ，
文章插图和一个目标数 ， S 。 现在你有两个符号 + 和 - 。 对于数组中的任意一个整数 ， 你都可以从 + 或 - 中选择一个符号添加在前面 。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数 。
示例
输入：nums: [1, 1, 1, 1, 1], S: 3输出：5解释：-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?一共有5种方法让最终目标和为3 。 提示- 数组非空 ， 且长度不会超过 20。
- 初始的数组的和不会超过 1000。
- 保证返回的最终结果能被 32 位整数存下 。
推荐阅读
- 大一非计算机专业的学生，如何利用寒假自学C语言
- 向日葵远程控制企业版客户端更新升级，优化远控UI适配SADDC内核算法
- 红米K40渲染图曝光：居中挖孔+后置四摄，这外观你觉得如何？
- 奋斗|该如何看待拼多多员工猝死：鼓励奋斗，也要保护好奋斗者
- 装机点不亮 如何简易排查硬件问题？
- 虾米音乐宣布关停！我的歌单如何导入QQ音乐、网易云音乐？
- 人脸识别设备主板如何选型 软硬整合大幅缩短开发时间
- Mini-LED产品效果究竟如何？
- 专家介绍如何判断智能手机被入侵：运行速度变慢、电池消耗过快以及卡顿
- 在谷歌算法更新之后2020年盗版网站流量锐减三分之一