网站做优化公司,建设网站的公司兴田德润怎么联系,微信公众号h5商城网站开发,单机小游戏在线玩网页给定一个正整数数组 nums 和一个整数 target 。 向数组中的每个整数前添加 ‘’ 或 ‘-’ #xff0c;然后串联起所有整数#xff0c;可以构造一个 表达式 #xff1a; 例如#xff0c;nums [2, 1] #xff0c;可以在 2 之前添加 ‘’ #xff0c;在 1 之前添加 ‘-’ ’ 或 ‘-’ 然后串联起所有整数可以构造一个 表达式 例如nums [2, 1] 可以在 2 之前添加 ‘’ 在 1 之前添加 ‘-’ 然后串联起来得到表达式 “2-1” 。 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例 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
提示
1 nums.length 20 0 nums[i] 1000 0 sum(nums[i]) 1000 -1000 target 1000
思路
看到数字的范围以及状态状态是可以从上一层转移的所以考虑动态规划 当然也可以使用dfs(思路会更简单一些)
状态表示 f[i][j]表示前i个数字总和为k的方案数量 这里每个数字都是必须选的 状态转移 由于每个数字都相当于是必须选的所以说不存在不选i的情况所以不能不选i直接从i-1层状态转移过来不选i这一情况的状态转移不用考虑了
状态转移方程 if(k-nums[i]m0)f[i][km]f[i-1][k-nums[i]m];if(knums[i]m2*m)f[i][km]f[i-1][knums[i]m];注意初始化的时候应该1,因为为第一个数为0的时候直接赋值为1会丢失一种情况
代码
class Solution {
public:int f[21][2100];int findTargetSumWays(vectorint nums, int target) {int nnums.size();int m0;for(int i0;in;i)mnums[i];if(mabs(target))return 0;memset(f,0,sizeof f);//f[i][k]表示第i个数总和为k的方案数//coutf[0][mnums[0]]endl;f[0][mnums[0]]1;//coutf[0][mnums[0]]endl;f[0][m-nums[0]]1;//这里必须是1因为nums[0]可能为0这时候如果1就少了一种情况//coutf[0][mnums[0]]endl;for(int i1;in;i)for(int k-m;km;k)//枚举总和{//f[i][km]max(f[i-1][km],f[i][km]); 由于第i个数不能不选所以说不能不选i进而从i-1这个状态直接转移过来if(k-nums[i]m0)f[i][km]f[i-1][k-nums[i]m];if(knums[i]m2*m)f[i][km]f[i-1][knums[i]m];}return f[n-1][mtarget];}
};运行结果
