目标和-背包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;
}