目标和-背包dp

494. 目标和 - 力扣（LeetCode）

Solution

多种方法;

1.普通递归搜索

2.带缓存表的递归

3.动态规划+平移技巧

4.转化为01背包问题

#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;

class Solution {
public:
	unordered_map<int, unordered_map<int, int>> mp;
	int findTargetSumWays(vector<int>& nums, int target) {
		return f3(nums, target);
	}

	//直接递归解法
	int f1(vector<int>& nums, int target, int i, int s) {
		int n = nums.size();
		if (i == n) return s == target ? 1 : 0;
		return f1(nums, target, i + 1, s + nums[i]) + f1(nums, target, i + 1, s - nums[i]);
	}

	//带缓存表的递归
	int f2(vector<int>& nums, int target, int i, int s, unordered_map<int, unordered_map<int, int>>& mp) {
		int n = nums.size();
		if (mp.count(i) && mp[i].count(s)) return mp[i][s];
		if (i == n) return s == target ? 1 : 0;
		int ans = f2(nums, target, i + 1, s + nums[i], mp) + f2(nums, target, i + 1, s - nums[i], mp);
		mp[i][s] = ans;
		return ans;
	}

	//动态规划
	// 新思路，转化为01背包问题
	// 思考1:
	// 虽然题目说nums是非负数组，但即使nums中有负数比如[3,-4,2]
	// 因为能在每个数前面用+或者-号
	// 所以[3,-4,2]其实和[3,4,2]会达成一样的结果
	// 所以即使nums中有负数，也可以把负数直接变成正数，也不会影响结果
	// 思考2:
	// 如果nums都是非负数，并且所有数的累加和是sum
	// 那么如果target>sum，很明显没有任何方法可以达到target，可以直接返回0
	// 思考3:
	// nums内部的数组，不管怎么+和-，最终的结果都一定不会改变奇偶性
	// 所以，如果所有数的累加和是sum，并且与target的奇偶性不一样
	// 那么没有任何方法可以达到target，可以直接返回0
	// 思考4(最重要):
	// 比如说给定一个数组, nums = [1, 2, 3, 4, 5] 并且 target = 3
	// 其中一个方案是 : +1 -2 +3 -4 +5 = 3
	// 该方案中取了正的集合为A = {1，3，5}
	// 该方案中取了负的集合为B = {2，4}
	// 所以任何一种方案，都一定有 sum(A) - sum(B) = target
	// 现在我们来处理一下这个等式，把左右两边都加上sum(A) + sum(B)，那么就会变成如下：
	// sum(A) - sum(B) + sum(A) + sum(B) = target + sum(A) + sum(B)
	// 2 * sum(A) = target + 数组所有数的累加和
	// sum(A) = (target + 数组所有数的累加和) / 2
	// 也就是说，任何一个集合，只要累加和是(target + 数组所有数的累加和) / 2
	// 那么就一定对应一种target的方式
	// 比如非负数组nums，target = 1, nums所有数累加和是11
	// 求有多少方法组成1，其实就是求，有多少种子集累加和达到6的方法，(1+11)/2=6
	// 因为，子集累加和6 - 另一半的子集累加和5 = 1(target)
	// 所以有多少个累加和为6的不同集合，就代表有多少个target==1的表达式数量
	// 至此已经转化为01背包问题了
	int f3(vector<int>& nums, int target) {
		int n = nums.size();
		int s = 0;
		for (int i = 0; i < n; ++i) {
			if (nums[i] < 0) nums[i] = -nums[i];
			s += nums[i];
		}
		if (target > s || -target > s) return 0;
		if ((s + target) % 2) return 0;
		int t = (s + target) / 2;
		vector<int>dp(t + 1, 0);
		dp[0] = 1;
		for (int i = 0; i < n; ++i) {
			for (int j = t; j >= nums[i]; --j) {
				dp[j] = dp[j] + dp[j - nums[i]];
			}
		}
		return dp[t];
	}
};

int main() {

	return 0;
}