目标和

悠悠 2023-02-23 09:25 118阅读 0赞

## 一、前言 ##

动态规划相关问题。

问题来源LeetCode 494

问题链接：[https://leetcode-cn.com/problems/target-sum][https_leetcode-cn.com_problems_target-sum]

## 二、题目 ##

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

**示例：**

输入：nums: [1, 1, 1, 1, 1], S: 3
    输出：5
    解释：
    -1+1+1+1+1 = 3
    +1-1+1+1+1 = 3
    +1+1-1+1+1 = 3
    +1+1+1-1+1 = 3
    +1+1+1+1-1 = 3
    一共有5种方法让最终目标和为3。

**提示：**

*  数组非空，且长度不会超过 20 。
 *  初始的数组的和不会超过 1000 。
 *  保证返回的最终结果能被 32 位整数存下。

## 三、思路 ##

这里提供了两种解法，一种是暴力法，直接看代码即可；一种是转换成01背包问题。转换过程：设数组中数据符号是+和是A，符合是-的和的绝对值是B，这组数字绝对值相加和为C。

A + B = C；A - B = S => A+B+A-B = C+S => 2A = C+S => A = (C+S)/2；C+S需要是偶数，我们只需要在数组中找到和为A就满足条件。

### 3.1 递推公式 ###

f(i,j) = f(i,j) + f(i, j - a[i]);  (j = [S,a[i]])
    f(0,0) = 1;

### 3.2 图解实例 ###

实例 a = \{ 2,3,4,2,2,3 \}， S= -4，求输出方法数？

创建一个数组dp\[7\]用于记录，满足目标的个数。为了方便计算我们将dp\[0\]设置为1。计算过程我们是从后往前计算。

1）只有一个数据a1=2

![20200707001821200.png][]

2）新加一个数据a2=3

![20200707001838584.png][]

3）新加一个数据a3=4

![20200707001856548.png][]

4）新加一个数据a4=2

![20200707001919684.png][]

5）新加一个数据a5=2

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70][]

6）新加一个数据a6=3

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 1][]

最终结果是5。

## 四、总结 ##

1.  理解转换过程；
2.  每加一个是数据，计算过程是从后往前计算；

## 五、编码实现 ##

//==========================================================================
    /**
    * @file    : 494_FindTargetSumWays.h
    * @blogs   :
    * @author  : niebingyu
    * @date    ：2020/07/06
    * @title   : 目标和
    * @purpose : 给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。
    *			 对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
    *			 返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
    *
    * 示例：
    *
    * 输入：nums: [1, 1, 1, 1, 1], S: 3
    * 输出：5
    * 解释：
    * -1+1+1+1+1 = 3
    * +1-1+1+1+1 = 3
    * +1+1-1+1+1 = 3
    * +1+1+1-1+1 = 3
    * +1+1+1+1-1 = 3
    *
    * 一共有5种方法让最终目标和为3。
    *
    * 提示：
    * 数组非空，且长度不会超过 20 。
    * 初始的数组的和不会超过 1000 。
    * 保证返回的最终结果能被 32 位整数存下。
    *
    * 来源：力扣（LeetCode）
    * 难度：困难
    * 链接：https://leetcode-cn.com/problems/target-sum
    */
    //==========================================================================
    #pragma once
    #include <iostream>
    #include <vector>
    #include <list>
    #include <algorithm>
    using namespace std;
    
    #define NAMESPACE_FINDTARGETSUMWAYS namespace NAME_FINDTARGETSUMWAYS {
    #define NAMESPACE_FINDTARGETSUMWAYSEND }
    NAMESPACE_FINDTARGETSUMWAYS
    
    // 暴力解法
    class Solution2 
    {
    public:
        int findTargetSumWays(vector<int>& nums, int S) 
        {
            return dfs(nums, S, 0);
        }
    
        int dfs(vector<int>& nums, int target, int left) 
        {
            if (target == 0 && left == nums.size()) 
                return 1;
            
            if (left >= nums.size()) 
                return 0;
    
            int ans = 0;
            ans += dfs(nums, target - nums[left], left + 1);
            ans += dfs(nums, target + nums[left], left + 1);
            return ans;
        }
    };
    
    // 动态规划解法
    class Solution 
    {
    public:
        int findTargetSumWays(vector<int>& nums, int S) 
        {
            long sum = 0;
            for (const int& n : nums) 
                sum += n;
    
            if ((S + sum) % 2 == 1 || S > sum) 
                return 0;
    
            S = (S + sum) / 2;
            vector<int> dp(S + 1, 0);
            dp[0] = 1;
    
            for (const int& n : nums) 
            {
                for (int j = S; j >= n; j--)
                {
                    dp[j] += dp[j - n];
                }
            }
    
            int ans = dp[S];
            return ans;
        }
    };
    
    以下为测试代码//
    // 测试 用例 START
    void test(const char* testName, vector<int>& nums, int S, int expect)
    {
        Solution s;
        int result = s.findTargetSumWays(nums, S);
        if (expect == result)
        {
            cout << testName << ", solution passed." << endl;
        }
        else
        {
            cout << testName << ", solution failed." << endl;
        }
    }
    
    void Test1()
    {
        vector<int>nums = { 2,3,4,2,2,3 };
        int S = -4;
        int expect = 5;
        
        test("Test1()", nums, S, expect);
    }
    NAMESPACE_FINDTARGETSUMWAYSEND
    // 测试 用例 END
    //
    
    void FindTargetSumWays_Test()
    {
        NAME_FINDTARGETSUMWAYS::Test1();
    }

**执行结果：**

![20200707002139845.png][]

[https_leetcode-cn.com_problems_target-sum]: https://leetcode-cn.com/problems/target-sum
[20200707001821200.png]: https://img-blog.csdnimg.cn/20200707001821200.png
[20200707001838584.png]: https://img-blog.csdnimg.cn/20200707001838584.png
[20200707001856548.png]: https://img-blog.csdnimg.cn/20200707001856548.png
[20200707001919684.png]: https://img-blog.csdnimg.cn/20200707001919684.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200707001937481.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200707001959428.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[20200707002139845.png]: https://img-blog.csdnimg.cn/20200707002139845.png