动态规划07-目标和

题目介绍

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

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

思路分析

本题跟简单的01背包问题有所不同，本题要求解的是实现装满背包的可能种类，所以本质上是一个排列问题。对于每个元素，只有加和减两种可能，最终要实现的就是让和是S，这里给出数学公式，假设将整个数组分成两个部分，一个是正数部分，另一个是负数部分的绝对值，两个部分的和是Sum，两个部分的差值就是S，将两个式子联立就能解出其中的一个部分的值是(S+Sum)/2。背包问题初具雏形！

1. 定义dp[j]的含义：填满容积为j的背包的方法有dp[j]种。
2. 确定转换关系：dp[j] += dp[j - sums[i]]，解释一下就是对于容积为j的包，当遍历到物品i的时候，其方法就是之前的方法（去掉sum[i]的容量的包的可能种类）加上当前的方法。
3. dp数组初始化：将dp[j]初始化我为1
4. 遍历顺序：nums内，targets外，同时内层循环倒序遍历
5. 举例推导成立

代码

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) sum += nums[i];
        if (abs(S) > sum) return 0; // 此时没有方案
        if ((S + sum) % 2 == 1) return 0; // 此时没有方案
        int bagSize = (S + sum) / 2;
        vector<int> dp(bagSize + 1, 0);
        dp[0] = 1;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = bagSize; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[bagSize];
    }
};