力扣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 <= max; sum++) {
// 如果上一步有求出和爲sum，那麼可以繼續計算下一步
if (dp[i - 1][sum + max] > 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 < -1000) {
return 0;
}
// 求出數組的和
int sumNums = 0;
for (int num : nums) {
sumNums += num;
}
// 新的目標和(sumNums + S) / 2
int newTarget = sumNums + S;
// 如果是奇數，那麼無法被2整除，不符合規則
if ((newTarget & 1) == 1) {
return 0;
}
newTarget = newTarget / 2;
// 正常的揹包問題，在nums中找幾個數，滿足和爲newTarget
// dp[i]表示從數組nums找出和爲i的組合情況
int[] dp = new int[newTarget + 1];
dp[0] = 1;
// 遍歷數組
for (int num : nums) {
// 更新dp
for (int sum = newTarget; sum >= num; sum--) {
dp[sum] += dp[sum - num];
}
}
return dp[newTarget];
}
}
提交OK，時間複雜度是`O(n * newTarget)`，其中，` newTarget = (target + sum(nums))/2`，和前面方法中的`max`相比，`sum(nums) <= max`，如果`target > max`，也會直接返回0，因此這個方法的時間複雜度更優。 ## 總結
以上就是這道題目我的解答過程了，不知道大家是否理解了。這道題主要是利用 動態規劃 ，優化時可以 找規律 ，轉化成正常的 揹包問題 。
有興趣的話可以訪問我的博客或者關注我的公衆號、頭條號，說不定會有意外的驚喜。
https://death00.github.io/
公衆號：健程之道
點擊此處留言
