當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

力扣--目标和

發布時間：2024/4/11 编程问答 25 豆豆

生活随笔收集整理的這篇文章主要介紹了力扣--目标和小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

力扣–目標和

文章目錄

力扣--目標和
- 一、題目描述
- 二、分析
- - 方法一：枚舉
  - 方法二：回溯【超時】
  - 方法三：消除重疊子問題【超時】
  - 方法四：動態規劃

一、題目描述

class Solution { public:int findTargetSumWays(vector<int>& nums, int S) {} };

二、分析

方法一：枚舉

class Solution { public://保存結果int count = 0;//start代表當前在nums的下標索引//sum代表當前+／-運算之后的結果//target代表目標結果void dp(vector<int>& nums, int start, int sum, int target){//遍歷完數組并且sum和target相等才++countif(start == nums.size()){if(target == sum){count++;}return ;}//+dp(nums,start + 1,sum + nums[start],target);//-dp(nums,start + 1,sum - nums[start],target);}int findTargetSumWays(vector<int>& nums, int S) {if(nums.empty()){return 0;}dp(nums, 0, 0, S);return count;} };

方法二：回溯【超時】

任何算法的核心都是窮舉，回溯算法就是一個暴力窮舉算法，回溯算法框架：

def backtrack(路徑, 選擇列表):if 滿足結束條件:result.add(路徑)returnfor 選擇 in 選擇列表:做選擇backtrack(路徑, 選擇列表)撤銷選擇

關鍵就是搞清楚什么是「選擇」，而對于這道題，「選擇」不是明擺著的嗎？
對于每個數字 nums[i]，我們可以選擇給一個正號 + 或者一個負號 -，然后利用回溯模板窮舉出來所有可能的結果，數一數到底有幾種組合能夠湊出 target 不就行了嘛？
偽碼思路如下：

def backtrack(nums, i):if i == len(nums):if 達到 target:result += 1returnfor op in { +1, -1 }:選擇 op * nums[i]# 窮舉 nums[i + 1] 的選擇backtrack(nums, i + 1)撤銷選擇

代碼

int result = 0;/* 主函數 */ int findTargetSumWays(int[] nums, int target) {if (nums.length == 0) return 0;backtrack(nums, 0, target);return result; }/* 回溯算法模板 */ void backtrack(int[] nums, int i, int rest) {// base caseif (i == nums.length) {if (rest == 0) {// 說明恰好湊出 targetresult++;}return;}// 給 nums[i] 選擇 - 號rest += nums[i];// 窮舉 nums[i + 1]backtrack(nums, i + 1, rest);// 撤銷選擇rest -= nums[i]; // 給 nums[i] 選擇 + 號rest -= nums[i];// 窮舉 nums[i + 1]backtrack(nums, i + 1, rest);// 撤銷選擇rest += nums[i]; }

有的讀者可能問，選擇 - 的時候，為什么是 rest += nums[i]，選擇 + 的時候，為什么是 rest -= nums[i] 呢，是不是寫反了？
不是的，「如何湊出 target」和「如何把 target 減到 0」其實是一樣的。我們這里選擇后者，因為前者必須給 backtrack 函數多加一個參數，我覺得不美觀：

void backtrack(int[] nums, int i, int sum, int target) {// base caseif (i == nums.length) {if (sum == target) {result++;}return;}// ... }

因此，如果我們給 nums[i] 選擇 + 號，就要讓 rest - nums[i]，反之亦然。
以上回溯算法可以解決這個問題，時間復雜度為 $O(2^N)$ ，N 為 nums 的大小。
進一步觀察發現這個回溯算法就是個二叉樹的遍歷問題：

void backtrack(int[] nums, int i, int rest) {if (i == nums.length) {return;}backtrack(nums, i + 1, rest - nums[i]);backtrack(nums, i + 1, rest + nums[i]); }

樹的高度就是 nums 的長度嘛，所以說時間復雜度就是這棵二叉樹的節點數，為 $O(2^N)$ ，其實是非常低效的。

方法三：消除重疊子問題【超時】

動態規劃之所以比暴力算法快，是因為動態規劃技巧消除了重疊子問題。
如何發現重疊子問題？看是否可能出現重復的「狀態」。對于遞歸函數來說，函數參數中會變的參數就是「狀態」，對于 backtrack 函數來說，會變的參數為 i 和 rest。
先抽象出遞歸框架：

void backtrack(int i, int rest) {backtrack(i + 1, rest - nums[i]);backtrack(i + 1, rest + nums[i]); }

舉個簡單的例子，如果 nums[i] = 0，會發生什么？

void backtrack(int i, int rest) {backtrack(i + 1, rest);backtrack(i + 1, rest); }

你看，這樣就出現了兩個「狀態」完全相同的遞歸函數，無疑這樣的遞歸計算就是重復的。
這就是重疊子問題，而且只要我們能夠找到一個重疊子問題，那一定還存在很多的重疊子問題。
因此，狀態 (i, rest) 是可以用備忘錄技巧進行優化的：

int findTargetSumWays(int[] nums, int target) {if (nums.length == 0) return 0;return dp(nums, 0, target); }// 備忘錄 HashMap<String, Integer> memo = new HashMap<>(); int dp(int[] nums, int i, int rest) {// base caseif (i == nums.length) {if (rest == 0) return 1;return 0;}// 把它倆轉成字符串才能作為哈希表的鍵String key = i + "," + rest;// 避免重復計算if (memo.containsKey(key)) {return memo.get(key);}// 還是窮舉int result = dp(nums, i + 1, rest - nums[i]) + dp(nums, i + 1, rest + nums[i]);// 記入備忘錄memo.put(key, result);return result; }

這個解法通過備忘錄消除了很多重疊子問題，效率有一定的提升，但是這就結束了嗎？

方法四：動態規劃

事情沒有這么簡單，先來算一算，消除重疊子問題之后，算法的時間復雜度是多少？其實最壞情況下依然是 $O(2^N)$ 。
為什么呢？因為我們只不過恰好發現了重疊子問題，順手用備忘錄技巧給優化了，但是底層思路沒有變，依然是暴力窮舉的回溯算法，依然在遍歷一棵二叉樹。
這只能叫對回溯算法進行了「剪枝」，提升了算法在某些情況下的效率，但算不上質的飛躍。
其實，這個問題可以轉化為一個子集劃分問題，而子集劃分問題又是一個典型的背包問題。動態規劃總是這么玄學，讓人摸不著頭腦……
首先，如果我們把 nums 劃分成兩個子集 A 和 B，分別代表分配 + 的數和分配 - 的數，那么他們和 target 存在如下關系：

sum(A) - sum(B) = target sum(A) = target + sum(B) sum(A) + sum(A) = target + sum(B) + sum(A) 2 * sum(A) = target + sum(nums)

綜上，可以推出 $s u m (A) = (t a r g e t + s u m (n u m s)) / 2$ ，也就是把原問題轉化成：nums 中存在幾個子集A，使得 A 中元素的和為 $(t a r g e t + s u m (n u m s)) / 2$ ？
類似的子集劃分問題我們前文經典背包問題：子集劃分講過，現在實現這么一個函數：

/* 計算 nums 中有幾個子集的和為 sum */ int subsets(int[] nums, int sum) {}//然后，可以這樣調用這個函數： int findTargetSumWays(int[] nums, int target) {int sum = 0;for (int n : nums) sum += n;// 這兩種情況，不可能存在合法的子集劃分if (sum < target || (sum + target) % 2 == 1) {return 0;}return subsets(nums, (sum + target) / 2); }

好的，變成背包問題的標準形式：
有一個背包，容量為 sum，現在給你 N 個物品，第 i 個物品的重量為 nums[i - 1]（注意 1 <= i <= N），每個物品只有一個，請問你有幾種不同的方法能夠恰好裝滿這個背包？
現在，這就是一個正宗的動態規劃問題了，下面按照我們一直強調的動態規劃套路走流程：
第一步要明確兩點，「狀態」和「選擇」。
對于背包問題，這個都是一樣的，狀態就是「背包的容量」和「可選擇的物品」，選擇就是「裝進背包」或者「不裝進背包」。
第二步要明確 dp 數組的定義。
按照背包問題的套路，可以給出如下定義：
dp[i][j] = x 表示，若只在前 i 個物品中選擇，若當前背包的容量為 j，則最多有 x 種方法可以恰好裝滿背包。
翻譯成我們探討的子集問題就是，若只在 nums 的前 i 個元素中選擇，若目標和為 j，則最多有 x 種方法劃分子集。
根據這個定義，顯然 dp[0][..] = 0，因為沒有物品的話，根本沒辦法裝背包；dp[..][0] = 1，因為如果背包的最大載重為 0，「什么都不裝」就是唯一的一種裝法。
我們所求的答案就是 dp[N][sum]，即使用所有 N 個物品，有幾種方法可以裝滿容量為 sum 的背包。
第三步，根據「選擇」，思考狀態轉移的邏輯。
回想剛才的 dp 數組含義，可以根據「選擇」對 dp[i][j] 得到以下狀態轉移：
如果不把 nums[i] 算入子集，或者說你不把這第 i 個物品裝入背包，那么恰好裝滿背包的方法數就取決于上一個狀態dp[i-1][j]，繼承之前的結果。
如果把 nums[i] 算入子集，或者說你把這第 i 個物品裝入了背包，那么只要看前 i - 1 個物品有幾種方法可以裝滿 j -nums[i-1] 的重量就行了，所以取決于狀態 dp[i-1][j-nums[i-1]]。
PS：注意我們說的 i 是從 1 開始算的，而數組 nums 的索引時從 0 開始算的，所以 nums[i-1] 代表的是第 i個物品的重量，j - nums[i-1] 就是背包裝入物品 i 之后還剩下的容量。
由于 dp[i][j] 為裝滿背包的總方法數，所以應該以上兩種選擇的結果求和，得到狀態轉移方程：
$d p [i] [j] = d p [i ? 1] [j] + d p [i ? 1] [j ? n u m s [i ? 1]]$ ;
然后，根據狀態轉移方程寫出動態規劃算法：

/* 計算 nums 中有幾個子集的和為 sum */ int subsets(int[] nums, int sum) {int n = nums.length;int[][] dp = new int[n + 1][sum + 1];// base casefor (int i = 0; i <= n; i++) {dp[i][0] = 1;}for (int i = 1; i <= n; i++) {for (int j = 0; j <= sum; j++) {if (j >= nums[i-1]) {// 兩種選擇的結果之和dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];} else {// 背包的空間不足，只能選擇不裝物品 idp[i][j] = dp[i-1][j];}}}return dp[n][sum]; }

然后，發現這個 dp[i][j] 只和前一行 dp[i-1][…] 有關，那么肯定可以優化成一維 dp：

/* 計算 nums 中有幾個子集的和為 sum */ int subsets(int[] nums, int sum) {int n = nums.length;int[] dp = new int[sum + 1];// base casedp[0] = 1;for (int i = 1; i <= n; i++) {// j 要從后往前遍歷for (int j = sum; j >= 0; j--) {// 狀態轉移方程if (j >= nums[i-1]) {dp[j] = dp[j] + dp[j-nums[i-1]];} else {dp[j] = dp[j];}}}return dp[sum]; }

對照二維 dp，只要把 dp 數組的第一個維度全都去掉就行了，唯一的區別就是這里的 j 要從后往前遍歷，原因如下：
因為二維壓縮到一維的根本原理是， $d p [j] 和 d p [j ? n u m s [i ? 1]]$ 還沒被新結果覆蓋的時候，相當于二維 dp 中的 $d p [i ? 1] [j] 和 d p [i ? 1] [j ? n u m s [i ? 1]]$ 。
那么，我們就要做到：在計算新的 dp[j] 的時候，dp[j] 和 dp[j-nums[i-1]] 還是上一輪外層 for循環的結果。
如果你從前往后遍歷一維 dp 數組，dp[j] 顯然是沒問題的，但是 dp[j-nums[i-1]] 已經不是上一輪外層 for循環的結果了，這里就會使用錯誤的狀態，當然得不到正確的答案。
完整C++代碼

class Solution { public:/* 計算 nums 中有幾個子集的和為 sum */int subsets(vector<int>& nums, int sum) {int n = nums.size();vector<int> dp (sum + 1,0);// base casedp[0] = 1;for (int i = 1; i <= n; i++) {// j 要從后往前遍歷for (int j = sum; j >= 0; j--) {// 狀態轉移方程if (j >= nums[i-1]) {dp[j] = dp[j] + dp[j-nums[i-1]];} else {dp[j] = dp[j];}}}return dp[sum];}int findTargetSumWays(vector<int>& nums, int S) {if(nums.empty()){return 0;}int sum = 0;for(auto e : nums){sum += e;}if (sum < S || (sum + S) % 2 == 1) {return 0;}int target = (sum + S) / 2;return subsets(nums, target);} };

現在，這道題算是徹底解決了。
總結一下，回溯算法雖好，但是復雜度高，即便消除一些冗余計算，也只是「剪枝」，沒有本質的改進
而動態規劃就比較玄學了，經過各種改造，從一個加減法問題變成子集問題，又變成背包問題，經過各種套路寫出解法，又搞出狀態壓縮，還得反向遍歷。

總結

以上是生活随笔為你收集整理的力扣--目标和的全部內容，希望文章能夠幫你解決所遇到的問題。

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