动态规划-背包题目——494.目的和

1.状态表现

    标题泉源

  

494.目的和——力扣

   测试用例 

  

   2.算法原理

  1.状态表现

起首我们须要将题目简化，这里须要找到能将数组组合盘算成为指定命字target的添加方式，那么我们就可以将数字分为两类，一类是前面添加"+"的，另一类则是添加"-"的，那么对这两类数字举行关系分析终极如下图得到了关于正数总和的表达式，因此就转化为将数组中的数字挑选出和恰恰为a的组合方法有几种，也就是背包题目
接下来就可以表现每个位置的状态，上面探求恰恰便是某个指定的数字，那么就创建一个二维的dp表来存储选取数字的范围以及当前已选数字之和，即
dp[j]：在[0,i]的区间选取的数字之和完全便是j的选取方式总数

2.状态转移方程

起首仍旧是背包题目的思绪，对末了一个位置举行分类讨论，起首判断当第i个位置不会选取，此时就找到dp[i-1][j]，判断此时的方法数；然后判断选取第i个位置的数，此时就须要探求到dp[i-1][j-nums[i-1]]这个位置的dp表的值，然后加到总方法数中去，固然须要判断j>=nums[i-1]
3.初始化

起首dp[0][0]肯定是一种方法，也就是在不选择任何数字此时的总和肯定为0那么就将dp[0][0]置为1，之后第一行其他位置代表不选数字但是此时的总和为j(j>=1)，这种环境肯定是不存在的，那么就置为0即可，然后对第一列来判断，此时第一列由于原数组中的数字大概为0，那么第一列的初始化就不确定，但是由于在后续中的判断条件肯定是j>=nums[i-1]，这就包管了在使用第一列时肯定不会出现越界的环境，那么不妨不初始化第一列，直接在循环中填写即可
4.填表次序

从上到下，每一行从左到右
5.返回值 

返回dp表末了一个位置的值即可
   3.实战代码

1. class Solution {
2. public:
3.     int findTargetSumWays(vector<int>& nums, int target)
4.     {
5.         int m = nums.size();
6.         int sum = 0;
7.         for(auto e : nums)
8.         {
9.             sum += e;
10.         }   
11.         int n = (sum + target) / 2;
12.         if(n < 0 || (sum + target) % 2 == 1)
13.         {
14.             return 0;
15.         }
16.         vector<vector<int>> dp(m+1,vector<int>(n+1));
17.         dp[0][0] = 1;
19.         for(int i = 1;i <= m;i++)
20.         {
21.             for(int j = 0;j <= n;j++)
22.             {
23.                 dp[i][j] += dp[i-1][j];
24.                 if(j >= nums[i-1])
25.                 {
26.                     dp[i][j] += dp[i-1][j-nums[i-1]];
27.                 }
28.             }
29.         }
30.         return dp[m][n];
31.     }
32. };

复制代码

  代码剖析 

  

   优化代码（空间优化）