力扣494——目标和
这道题主要是利用动态规划进行求解,优化的时候可以找规律,转化成正常的背包问题。
原题
给定一个非负整数数组,a1, a2, …, an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例 1:
输入: 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位整数存下。
原题url:https://leetcode-cn.com/problems/target-sum/
解题
简单递归
最简单的方法就是计算出所有的可能性,如果最终结果等于目标值,则说明该情况可以。直接看一下代码:
public class Solution { int result = 0; public int findTargetSumWays(int[] nums, int S) { // 递归 findTargetSumWays(nums, S, 0, 0); // 返回最终结果 return result; } // index : 当前计算到数组中的位置 // sum : 当前的总和 public void findTargetSumWays(int[] nums, int S, int index, int sum) { // 遍历是否结束 if (index == nums.length) { // 如果总和等于S,则最终结果+1 if (sum == S) { result++; } return; } // 针对当前的数值,有加和减两种情况 findTargetSumWays(nums, S, index + 1, sum + nums[index]); findTargetSumWays(nums, S, index + 1, sum - nums[index]); } }
方法很简单,但是时间复杂度太高, O(2^n)
,执行用时在 java 中也只打败了 31.65%
,看来确实不够好。
简单的动态规划
这其实类似于 背包问题
,有容量要求(部分数字之和等于目标值)。首先我们来想一下状态转移方程:
我们用二维数组 dp[i][j]
表示用数组中的前 i
个元素,组成和为 j
的方案数。考虑第 i
个数 nums[i]
,它可以被添加 + 或 -,因此状态转移方程如下:
dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j + nums[i]]
也可以写成递推的形式:
dp[i][j + nums[i]] += dp[i - 1][j] dp[i][j - nums[i]] += dp[i - 1][j]
因为题目中提到所有数的和不超过 1000,那么 j 的最小值可以达到 -1000。在 java 中,是不允许数组的下标为负数的,因此我们需要给 dp[i][j]
的第二维预先增加 1000,那么新的递推关系如下:
dp[i][j + nums[i] + 1000] += dp[i - 1][j + 1000] dp[i][j - nums[i] + 1000] += dp[i - 1][j + 1000]
接下来我们看看代码:
public class Solution { public int findTargetSumWays(int[] nums, int S) { if (S > 1000 || S < -1000) { return 0; } // 求和的最大值 int max = 1000; // 初始的数组的和不会超过1000,因此最大为1000,最小为-1000 int[][] dp = new int[nums.length][max * 2 + 1]; // 针对nums[0],先求出第一步 dp[0][nums[0] + max] = 1; dp[0][-nums[0] + max] += 1; // 遍历数组 for (int i = 1; i < nums.length; i++) { for (int sum = -max; sum 0) { dp[i][nums[i] + sum + max] += dp[i - 1][sum + max]; dp[i][-nums[i] + sum + max] += dp[i - 1][sum + max]; } } } return dp[nums.length - 1][S + max]; } }
提交OK,时间复杂度为 O(N ∗ max)
,max 代表数组中所有数字之和的最大值,执行用时在 java 中打败了 58.91%
,看来还有很大的提升空间。
动态规划 + 找规律
我们想一下,之所以上面的方法会涉及到 max,因为所谓的 求和
,并不只是加法,也可以用减法。这和我们一般理解的 背包问题
还是有所不同的,那么我们是否可以将本题转换成真正意义上的 背包问题
呢?
首先,我们可以将这组数看成两部分,P 和 N,其中 P 使用正号,N 使用负号,那么可以推导出一下关系:
1、target = sum(P) - sum(N) 2、sum(nums) = sum(P) + sum(N) 由1可以得出:sum(P) = target + sum(N) 由2可以得出:sum(N) = sum(nums) - sum(P) 综合以上,可以得出: sum(P) = (target + sum(nums)) / 2
因此只要找到一个子集,令它们都取正号,并且和等于 (target + sum(nums))/2,就证明存在解,这就属于正常的 0-1背包问题
的范畴了。需要注意 target + sum(nums)
必须为偶数,否则 sum(P) 就是小数了,这和题目要求的所有数都是 非负整数
不符。
接下来我们看看代码:
public class Solution { public int findTargetSumWays(int[] nums, int S) { if (S > 1000 || S = num; sum--) { dp[sum] += dp[sum - num]; } } return dp[newTarget]; } }
提交OK,时间复杂度是`O(n * newTarget)`,其中,` newTarget = (target + sum(nums))/2`,和前面方法中的`max`相比,`sum(nums) max`,也会直接返回0,因此这个方法的时间复杂度更优。 ## 总结
以上就是这道题目我的解答过程了,不知道大家是否理解了。这道题主要是利用 动态规划
,优化时可以 找规律
,转化成正常的 背包问题
。
有兴趣的话可以访问我的博客或者关注我的公众号、头条号,说不定会有意外的惊喜。
https://death00.github.io/
公众号:健程之道
点击此处留言