（算法） ⽬标和————＜动态规划＞

1. 题⽬链接：494. ⽬标和

2. 题⽬描述：

3. 解法（动态规划）：

算法思路：

本题可以直接⽤「暴搜」的⽅法解决。但是稍微⽤数学知识分析⼀下，就能转化成我们常⻅的「背 包模型」的问题。 设我们最终选取的结果中，前⾯加 + 号的数字之和为 a ，前⾯加 - 号的数字之和为 b ，整个数组 的总和为 sum ，于是我们有：

        ▪ a + b = sum

        ▪ a - b = target 上⾯两个式⼦消去 b 之后，可以得到 a = (sum + target) / 2 也就是说，我们仅需在 nums 数组中选择⼀些数，将它们凑成和为 (sum + target) / 2 即 可。

问题就变成了 416. 分割等和⼦集 这道题。 我们可以⽤相同的分析模式，来处理这道题。

1. 状态表⽰：

dp[i][j] 表⽰：在前 i 个数中选，总和正好等于 j ，⼀共有多少种选法。

2. 状态转移⽅程：

⽼规矩，根据「最后⼀个位置」的元素，结合题⽬的要求，我们有「选择」最后⼀个元素或者「不 选择」最后⼀个元素两种策略：

        i. 不选 nums[i] ：那么我们凑成总和 j 的总⽅案，就要看在前 i - 1 个元素中选，凑 成总和为 j 的⽅案数。根据状态表⽰，此时 dp[i][j] = dp[i - 1][j] ；

        ii. 选择 nums[i] ：这种情况下是有前提条件的，此时的 nums[i] 应该是⼩于等于 j 。 因为如果这个元素都⽐要凑成的总和⼤，选择它就没有意义呀。那么我们能够凑成总和为 j 的⽅案数，就要看在前 i - 1 个元素中选，能否凑成总和为 j - nums[i] 。

根据 状态表⽰，此时 dp[i][j] = dp[i - 1][j - nums[i]]

综上所述，两种情况如果存在的话，应该要累加在⼀起。因此，状态转移⽅程为：  dp[i][j] = dp[i - 1][j] if(nums[i - 1] <= j) dp[i][j] = dp[i][j] += dp[i - 1][j - nums[i - 1]]

3. 初始化：

由于需要⽤到「上⼀⾏」的数据，因此我们可以先把第⼀⾏初始化。 第⼀⾏表⽰不选择任何元素，要凑成⽬标和 j 。只有当⽬标和为 0 的时候才能做到，因此第⼀ ⾏仅需初始化第⼀个元素 dp[0][0] = 1

4. 填表顺序：

根据「状态转移⽅程」，我们需要「从上往下」填写每⼀⾏，每⼀⾏的顺序是「⽆所谓的」。

5. 返回值：

根据「状态表⽰」，返回 dp[n][aim] 的值。 其中 n 表⽰数组的⼤⼩， aim 表⽰要凑的⽬标和。

6. 空间优化：

所有的「背包问题」，都可以进⾏空间上的优化。 对于 01背包类型的，我们的优化策略是：

        i. 删掉第⼀维；

        ii. 修改第⼆层循环的遍历顺序即可。 

C++ 优化前的算法代码: 

class Solution 
{
public:
    int findTargetSumWays(vector<int>& nums, int target) 
    {
        //求和
        int sum=0;
        for(auto& key:nums)
        {
            sum+=key;
        }
        //建表
        int m=nums.size(),n=(target+sum)/2;
        //边界情况
        //奇数除二结果不为整数，找不到
        cout<<n<<endl;
        if(n < 0 || (sum + target) % 2) 
        {
            return 0;
        }
        //在前i个元素中选择出和为j的子序列个数
        vector<vector<int>>dp(m+1,vector<int>(n+1));
        //初始化
        dp[0][0]=1;
        //填表
        for(int i=1;i<=m;i++)
        {
            //第一列还未初始化，故j从0开始
            for(int j=0;j<=n;j++)
            {
                //不选
                dp[i][j]=dp[i-1][j];
                //选
                if(j-nums[i-1]>=0)
                {
                    dp[i][j]+=dp[i-1][j-nums[i-1]];
                }
            }
        }
        //返回值
        return dp[m][n];
    }
};

C++ 空间优化后的算法代码:

class Solution 
{
public:
    int findTargetSumWays(vector<int>& nums, int target) 
    {
        //求和
        int sum=0;
        for(auto& key:nums)
        {
            sum+=key;
        }
        //建表
        int m=nums.size(),n=(target+sum)/2;
        //边界情况
        //奇数除二结果不为整数，找不到
        cout<<n<<endl;
        if(n < 0 || (sum + target) % 2) 
        {
            return 0;
        }
        //在前i个元素中选择出和为j的子序列个数
        vector<int>dp(n+1);
        //初始化
        dp[0]=1;
        //填表
        for(int i=1;i<=m;i++)
        {
            //第一列还未初始化，故j从0开始
            for(int j=n;j>=0;j--)
            {
                if(j-nums[i-1]>=0)
                {
                    dp[j]+=dp[j-nums[i-1]];
                }
            }
        }
        //返回值
        return dp[n];
    }
};

Java 优化前的算法代码:

class Solution
{
 public int findTargetSumWays(int[] nums, int target)
 {
	int n = nums.length, sum = 0;
	 for(int x : nums) sum += x;
	 int aim = (sum + target) / 2;
	// 处理?下边界情况
	if(aim < 0 || (sum + target) % 2 == 1) return 0;
	int[][] dp = new int[n + 1][aim + 1];
	dp[0][0] = 1;
	for(int i = 1; i <= n; i++)
		 for(int j = 0; j <= aim; j++){
			 dp[i][j] = dp[i - 1][j];
			 if(j >= nums[i - 1])
				dp[i][j] += dp[i - 1][j - nums[i - 1]];
		 }
	return dp[n][aim];
 }
}

Java 空间优化后的算法代码:

class Solution
{
 public int findTargetSumWays(int[] nums, int target)
 {
	int n = nums.length, sum = 0;
	for(int x : nums) sum += x;
	int aim = (sum + target) / 2;
	 // 处理?下边界情况
	 if(aim < 0 || (sum + target) % 2 == 1) return 0;
	 int[] dp = new int[aim + 1];
	 dp[0] = 1;
	 for(int i = 1; i <= n; i++)
		 for(int j = aim; j >= nums[i - 1]; j--) // 注意修改遍历顺序
			dp[j] += dp[j - nums[i - 1]];
	return dp[aim];
 }
}