文章目錄

• 題目描述
• 思路 && 代碼
• • • 1. 動態規劃 O($n^2$)、O($n^2$)（最方便理解，初版）
    • 2. 轉換成 01 背包問題 O($n^2$)、O($n$)
    • 二刷
    • • • 離譜！添加了測試用例，上面的代碼需要添加負數條件了（見下面的代碼）

打卡第十五天～繼續加油！

題目描述

• 和上一道分割等和子集的做法很像
• 這里代碼迭代了很多次，但是時間復雜度是一樣的，只是空間復雜度、耗時不斷優化。
  
  

思路 && 代碼

1. 動態規劃 O($n^2$)、O($n^2$)（最方便理解，初版）

• dp[i][j]：下標[0 ~ i]構成的數集，能得到 j - sum 的情況種數
• 因為nums[ ]可構成元素范圍為[-sum, sum]，因此開出[2 * sum + 1]的列數組。
  其中[0] 代表 -sum，[2 * sum] 代表 [sum]，以此類推。
• 注意：初始化時，nums[0] 可能等于 -nums[0]，因此要用到 +=，而非 = 。
• 狀態轉移：對于當前的 j，分成 +nums[i]，和-nums[i]的情況，對上一行的值進行選取即可。
• 缺陷：空間復雜度不方便通過滾動數組的方式進行優化，因為狀態轉移方程的過程中，不但用到了前面的元素，還用到的后面的元素。解決方法：轉換成01背包問題

class Solution {public int findTargetSumWays(int[] nums, int target) {int sum = 0;for(int temp : nums) {sum += temp;}// 全正 or 全負，不在范圍的情況if(sum < target || -sum > target) {return 0;}// dp[i][j]：下標[0 ~ i]構成的數集，能得到 j - sum 的情況種數int top = 2 * sum + 1;int[][] dp = new int[nums.length][top];// 初始化：只取第一個元素，只能給 nums[0] 和 -nums[0] 帶來 1 個種數dp[0][sum + nums[0]] = 1;// 注意：存在 nums[0] == -nums[0] 的情況，因此這邊要用 +=dp[0][sum - nums[0]] += 1;// 狀態轉移for(int i = 1; i < nums.length; i++) {for(int j = 0; j < top; j++) {// Case 1：第 i 個元素取 + if(j >= nums[i]) {dp[i][j] = dp[i - 1][j - nums[i]];}// Case 2: 第 i 個元素取 -if(j + nums[i] < top) {dp[i][j] += dp[i - 1][j + nums[i]];}}}return dp[nums.length - 1][target + sum];} }

2. 轉換成 01 背包問題 O($n^2$)、O($n$)

• 實際上，題目可以這樣轉換成01背包問題：把 - 當成 0，不選；把 + 當成 1，選。
• 原本的(-nums) + (+nums) == target，表達式左邊和右邊都加上 sum，就轉換成
  0 + 2 * (+nums) == sum + target，方便起見，我們可以再進行除2操作，變成
  +nums == (sum + target) / 2。
• 注意：由此可推出，如果(sum + target) 為奇數，說明不存在對應的 +nums 序列，也就是不可取。
• 接下來就可以正常地進行 01背包 的動態規劃了～
• 滾動數組：逆序，現在沒有減法的情況下，可以保證無后效性

class Solution {public int findTargetSumWays(int[] nums, int target) {int sum = 0;for(int temp : nums) {sum += temp;}// 不在范圍的情況 && 奇數無法匹配到選取方式（可證）if(sum < target || (sum + target) % 2 == 1) {return 0;}// 轉換成 01背包：-號轉成不取；+號轉成取，兩倍// 實際上，只要考慮到 target + sum 即可，后面的和結果無關int top = (sum + target) / 2 + 1;// dp[i][j]：下標[0 ~ i]構成的數集，能得到 j - sum 的情況種數int[] dp = new int[top];// 初始化：第一個元素不取，只能給 0 帶來 1 個種數dp[0] = 1;// 狀態轉移for(int i = 0; i < nums.length; i++) {for(int j = top - 1; j >= nums[i]; j--) {// Case 1：取第 i 個元素dp[j] += dp[j - nums[i]];// Case 2: 不取第 i 個元素（一維情況下相當于不用考慮）}}return dp[top - 1];} }

• 來個無注釋版代碼吧，方便直接看代碼：

class Solution {public int findTargetSumWays(int[] nums, int target) {int sum = 0;for(int temp : nums) {sum += temp;}if(sum < target || (sum + target) % 2 == 1) {return 0;}int top = (sum + target) / 2 + 1;int[] dp = new int[top];dp[0] = 1;for(int i = 0; i < nums.length; i++) {for(int j = top - 1; j >= nums[i]; j--) {dp[j] += dp[j - nums[i]];}}return dp[top - 1];} }

二刷

離譜！添加了測試用例，上面的代碼需要添加負數條件了（見下面的代碼）

class Solution {public int findTargetSumWays(int[] nums, int target) {// 轉換成背包：+取兩次，-不取。target 相當于加了一次 sumfor(int temp : nums) {target += temp;}// 偶數之和不能為奇數 || 非負數之和不能為負if(target % 2 == 1 || target < 0) {return 0;}target /= 2;int[] dp = new int[target + 1];// 邊界處理：0的組合法有一個（都不取）dp[0] = 1;for(int i = 0; i < nums.length; i++) {for(int j = target; j >= nums[i]; j--) {// 相當于，這一輪的結果 = 上一輪的結果 + 這一輪的添加dp[j] += dp[j - nums[i]];}}return dp[target];} }

• 無注釋版，11行有效代碼

class Solution {public int findTargetSumWays(int[] nums, int target) {for(int temp : nums) {target += temp;}if(target % 2 == 1 || target < 0) {return 0;}target /= 2;int[] dp = new int[target + 1];dp[0] = 1;for(int i = 0; i < nums.length; i++) {for(int j = target; j >= nums[i]; j--) {dp[j] += dp[j - nums[i]];}}return dp[target];} } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的【LeetCode笔记】494. 目标和（Java、动态规划、背包问题、滚动数组）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。