@@ -28,4 +28,106 @@ private void backtrack(int[] nums, int index, int sum, int target) {
2828 backtrack (nums , index + 1 , sum + nums [index ], target );
2929 backtrack (nums , index + 1 , sum - nums [index ], target );
3030 }
31+ }
32+
33+
34+ /*
35+ 动态规划，0-1背包，二维dp数组
36+ 1、题目解析：
37+ 每个数字都有两种状态：被进行“+”，或者被进行“-”，因此可以将数组分成A和B两个部分：A部分的数字全部进行“+”操作，B部分的数字全部进行“-”操作。
38+ 设数组的和为sum，A部分的和为sumA，B部分的和为sumB，根据上面的分析，我们可以得出：
39+ sumA + sumB = sum (1)
40+ sumA - sumB = target (2)
41+ 将(1)式与(2)式相加，可以得到：2sumA = sum + target (3) 即：sumA = (sum + target) / 2
42+ 自此，原问题可以转化为0-1背包问题：有一些物品，第 i 个物品的重量为nums[i]，背包的容量为sumA，问：有多少种方式将背包【恰好装满】
43+ 2、数据校验：由公式推导得出的sumA，即bagSize，必须为整数且大于0，否则不能凑出。
44+ 3、定义dp数组：dp[i][j] 表示在前 i 个数字中，凑出和为 j 的组合数，即方法数
45+ 注意是求组合数，不是排列数，因为数组是有序的，只是在数字前面添加符号，不能改变数字的顺序。
46+ 4、状态转移方程：
47+ if (j < nums[i - 1]) dp[i][j] = dp[i - 1][j]; // 容量不够放，所以只能选择不放
48+ else dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]]; // 容量够放，可以将 不放时装满 和 放时装满 的组合数相加
49+ 不放 放
50+ 5、初始化：dp[i][0] 表示在前i个数字中，凑出和为0的组合数，容量不够放所以选择都不放时和为0，有1种方法，因此dp[0][0] = 1
51+ 6、遍历dp数组填表：先遍历数字，再遍历背包，背包正序遍历。数字应该从第1个数字开始，而背包应该从容量为0开始。
52+ 因为，题目中指出了nums[i] >=0，即可能为0，因此需要考虑到背包容量也为0的情况。
53+ 比如，第1个数字为0，背包容量也为0时，有两种选择：选择0 或者 不选，这两种选择都可以填满容量为0的背包
54+ 7、返回结果：最后一个状态就是结果
55+
56+ nums=[0,1,2,5]，target=4，行代表数字，列代表背包容量，首列初始化为1，从上到下，从左到右更新
57+ ----→
58+ | 1 0 0 0 0 0 0
59+ | 2 0 0 0 0 0 0
60+ ↓ 2 2 0 0 0 0 0
61+ 2 2 2 2 0 0 0
62+ 2 2 2 2 0 2 2
63+ */
64+ class Solution {
65+ public int findTargetSumWays (int [] nums , int target ) {
66+ int n = nums .length ;
67+ int sum = 0 ;
68+ for (int num : nums ) {
69+ sum += num ;
70+ }
71+ if ((sum + target ) % 2 != 0 ) {
72+ return 0 ;
73+ }
74+ int bagSize = (sum + target ) / 2 ;
75+ if (bagSize < 0 ) {
76+ return 0 ;
77+ }
78+ int [][] dp = new int [n + 1 ][bagSize + 1 ];
79+ for (int i = 0 ; i <= n ; i ++) {
80+ dp [i ][0 ] = 1 ;
81+ }
82+ for (int i = 1 ; i <= n ; i ++) {
83+ for (int j = 0 ; j <= bagSize ; j ++) {
84+ if (j < nums [i - 1 ]) {
85+ dp [i ][j ] = dp [i - 1 ][j ];
86+ } else {
87+ dp [i ][j ] = dp [i - 1 ][j ] + dp [i - 1 ][j - nums [i - 1 ]];
88+ }
89+ }
90+ }
91+ return dp [n ][bagSize ];
92+ }
93+ }
94+
95+
96+ /*
97+ 动态规划，0-1背包，一维dp数组
98+ 1、题目简化：有一些物品，第 i 个物品的重量为nums[i]，背包的容量为sumA，求有多少种方式将背包【恰好装满】
99+ 2、定义dp数组：dp[j] 表示凑出和为 j 的组合数，即方法数
100+ 3、状态转移方程：dp[j] = dp[j] + dp[j - num];
101+ 1）一维数组是滚动数组，每一轮滚动遍历中，未遍历的表示上一轮的旧状态，正在遍历的表示正在计算的状态，遍历过的表示本轮的新状态
102+ 2）等式右侧 dp[j] 表示前 i-1 个物品凑出和为 j 的组合数，在本轮中表示“不放”第i个物品就凑出和为j的组合数
103+ 3）等式右侧 dp[j - num] 表示前 i-1 个物品凑出和为 j-nums[i] 的组合数，在本轮中表示“放”第i个物品刚好凑出和为j的组合数
104+ 4）等式左侧 dp[j] 表示前 i 个物品凑出和为 j 的组合数，是由“不放”和“放”两种情况下凑出和为j的组合数相加
105+ 5）本轮遍历中，背包容量不够放时，只能选择不放，旧状态就是“不放”，所以只遍历背包容量足够的情况即可(j >= num)
106+ 4、初始化：dp[0] = 1; 装满容量为0的背包，有1种方法，就是装0件物品
107+ 5、遍历dp数组填表：先遍历数字，再遍历背包，背包倒序遍历
108+ 6、返回结果：最后一个状态就是结果
109+ */
110+ class Solution {
111+ public int findTargetSumWays (int [] nums , int target ) {
112+ int n = nums .length ;
113+ int sum = 0 ;
114+ for (int num : nums ) {
115+ sum += num ;
116+ }
117+ if ((sum + target ) % 2 != 0 ) {
118+ return 0 ;
119+ }
120+ int bagSize = (sum + target ) / 2 ;
121+ if (bagSize < 0 ) {
122+ return 0 ;
123+ }
124+ int [] dp = new int [bagSize + 1 ];
125+ dp [0 ] = 1 ;
126+ for (int num : nums ) {
127+ for (int j = bagSize ; j >= num ; j --) {
128+ dp [j ] += dp [j - num ];
129+ }
130+ }
131+ return dp [bagSize ];
132+ }
31133}
0 commit comments