目标和——动态规划的实践

一、题目

给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

二、解析

01背包其实不是这种解法的重点，重点是怎么把题目转化成求解01背包的形式。

如果只是单纯的求解和为某个S的组合个数，那就是01背包。。。

但是这题目中不仅有加，还有减，就得进行一个转化了。

思路就是把整个集合看成两个子集，Q表示整个集合，P表示正数子集，N表示负数子集， T表示目标和，用S(X)S(X)S(X)表示集合的求和函数，集合中均为非负数，N集合是指选中这部分元素作为负数子集。

也就是：正数集的和的两倍 == 等于目标和 + 序列总和

所以问题就转换成了，找到一个正数集P，其和的两倍等于目标和+序列总和。。。

简单吧，完全就是01背包了嘛！！！

对于01背包，其实我都差不多背下来了，你会发现背了以后，写着写着，就理解了。

需要注意的是，虽然序列总和不超过1000，但是S可是会接近int的上界。。。很容易出现超过整型范围的操作。

三、代码

class Solution {
	public:
		int findTargetSumWays(vector<int>& nums, int S) {
			long sum = 0;
			for (const int &it : nums) sum += it;
			if ((S + sum) % 2 == 1 || S > sum) return 0;
			S = (S + sum) / 2;
			int *dp = new int[S + 1];
			memset(dp, 0, (S + 1) * sizeof(int));
			dp[0] = 1;
			for (const int &it : nums) {
				for (int j = S; j >= it; j--)
					dp[j] += dp[j - it];
			}
			int ans = dp[S];
			delete[] dp;
			return ans;
		}
	};

参考：