（2021复旦机试）目标和+背包问题模板

目标和（LeetCode经典背包问题）

背包分类的模板：

1. 0/1背包：外循环nums,内循环target,target倒序且target>=nums[i];
2. 完全背包：外循环nums,内循环target,target正序且target>=nums[i];
3. 分组背包：这个比较特殊，需要三重循环：外循环背包bags,内部两层循环根据题目的要求转化为1,2,3三种背包类型的模板

问题分类的模板：

1. 最值问题: dp[i] = max/min(dp[i], dp[i-nums]+1)或dp[i] = max/min(dp[i], dp[i-num]+nums);
2. 存在问题(bool)：dp[i]=dp[i]||dp[i-num];
3. 组合问题：dp[i]+=dp[i-num];------二维情况： dp[i][j] = dp[i-1][j] + dp[i][j - nums[i-1]]
4. 参考文章

关键点：dp数组含义、边界条件设计、转移方程设计、背包容量的变通设计

方法一：递归法

class Solution {
public:
    void countWays(vector<int> nums,int sums, int index,int target,int& count){
        if(index == nums.size()) {
            if(sums == target) {
                count++;
            }
            return;
        }
        countWays(nums,sums+nums[index],index+1,target,count);
        countWays(nums,sums-nums[index],index+1,target,count);
    }
    int findTargetSumWays(vector<int>& nums, int target) {
        int count=0;
        countWays(nums,0,0,target,count);
        return count;
    }
};

方法二：动态规划法

其中neg即为背包的最大容量，即要找的最的解决方案，dp[n][neg]即为具体的方案数,定义package = neg;

• dp[i][j]定义：以nums[i]为结尾的元素的和为j的方案的个数
• 边界条件：dp[0][0]=1 背包容量是0，选择的数字也是0个，一共有1种方案，另外dp[0][i] =0 ,i∈[0, package]无论背包容量多大，背包中能放入的物品只有0个数字，因此方案只有0个。
• 转移方程：

public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for(auto x : nums) sum += x;
        int diff = sum - target;
        if(diff % 2 != 0 || diff < 0) {
            return 0;
        }
        int package = diff / 2;
        int n = nums.size();
        vector<vector<int>> dp(n+1, vector<int>(package + 1, 0 ));
        //1.边界条件处理
        dp[0][0] = 1;//  另外dp[0][i] i∈[0, package]
        //2. dp主过程
        for(int i=1;i<=n;i++) {
            for(int j=0;j<=package;j++) {
                int curNum = nums[i-1];
                if(curNum <= j) {//当前数字可以放入背包的场景，可以选择放入，也可选择不放入对应的放法都需要被考虑,所以需要相加
                    dp[i][j] = dp[i-1][j] + dp[i-1][j - curNum]; 
                }else{ //   当前数字无法放入，那么j的放入方案就只有dp[i-1][j]种
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[n][package];
    }
};