題目：

給你一個(gè)非負(fù)整數(shù)數(shù)組 nums 和一個(gè)整數(shù) target 。

向數(shù)組中的每個(gè)整數(shù)前添加 ‘+’ 或 ‘-’ ，然后串聯(lián)起所有整數(shù)，可以構(gòu)造一個(gè) 表達(dá)式

例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串聯(lián)起來得到表達(dá)式 “+2-1” 。
返回可以通過上述方法構(gòu)造的、運(yùn)算結(jié)果等于 target 的不同 表達(dá)式 的數(shù)目。

示例 1：

輸入：

nums = [1,1,1,1,1], target = 3

輸出：

5

解釋：

一共有 5 種方法讓最終目標(biāo)和為 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
+1 + 1 + 1 + 1 - 1 = 3

示例 2：

輸入：

nums = [1], target = 1

輸出：

1

提示：

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 1000
• 0 <= sum(nums[i]) <= 1000
• -1000 <= target <= 1000

思路：

本題可以用回溯來解決（但是會超時(shí)），也可以用動(dòng)態(tài)規(guī)劃中的01背包來解決，
如何轉(zhuǎn)化為01背包問題呢。

假設(shè)加法的總和為x，那么減法對應(yīng)的總和就是sum - x。

所以我們要求的是 x - (sum - x) = target

x = (target + sum) / 2

此時(shí)問題就轉(zhuǎn)化為，裝滿容量為x的背包，有幾種方法。

這里的x，就是bagSize，也就是我們后面要求的背包容量。

大家看到(target + sum) / 2 應(yīng)該擔(dān)心計(jì)算的過程中向下取整有沒有影響。

這么擔(dān)心就對了，例如sum 是5，S是2的話其實(shí)就是無解的，所以：

        # 如果nums的和與target的和的奇偶性不同，無法得到目標(biāo)和為target的子集
        if (sum(nums) + target) % 2 == 1:
            return 0

同時(shí)如果 S的絕對值已經(jīng)大于sum，那么也是沒有方案的。

        # 如果目標(biāo)和的絕對值大于nums的和，無法得到目標(biāo)和為target的子集
        if abs(target) > sum(nums):
            return 0

再回歸到01背包問題，為什么是01背包呢？

因?yàn)槊總€(gè)物品（題目中的1）只用一次

這次和之前遇到的背包問題不一樣了，之前都是求容量為j的背包，最多能裝多少。

本題則是裝滿有幾種方法。其實(shí)這就是一個(gè)組合問題了。

動(dòng)態(tài)規(guī)劃五部曲：

1. 確定dp數(shù)組以及下標(biāo)的含義

dp[j] 表示：填滿j（包括j）這么大容積的包，有dp[j]種方法

2. 確定遞推公式

有哪些來源可以推出dp[j]呢？

只要搞到nums[i]，湊成dp[j]就有dp[j - nums[i]] 種方法。

例如：dp[j]，j 為5，

• 已經(jīng)有一個(gè)1（nums[i]） 的話，有 dp[4]種方法 湊成 dp[5]。
• 已經(jīng)有一個(gè)2（nums[i]） 的話，有 dp[3]種方法 湊成 dp[5]。
• 已經(jīng)有一個(gè)3（nums[i]） 的話，有 dp[2]中方法 湊成 dp[5]。
• 已經(jīng)有一個(gè)4（nums[i]） 的話，有 dp[1]中方法 湊成 dp[5]。
• 已經(jīng)有一個(gè)5（nums[i]） 的話，有 dp[0]中方法 湊成 dp[5]。

那么湊整dp[5]有多少方法呢，也就是把 所有的 dp[j - nums[i]] 累加起來。

dp[j] += dp[j - nums[i]]

這個(gè)跟爬樓梯（力扣：70爬樓梯）和不同路徑（力扣：62.不同路徑）的思路有點(diǎn)類似，現(xiàn)在在重新分析一下：
現(xiàn)在有dp[4]種方法湊成4,你手上還有一個(gè)數(shù)字1，那么湊成5的話有幾種方法？ 還是dp[4]種方法！為什么不是dp[4] + 1 種方法呢？因?yàn)檫@個(gè)數(shù)字1是確定只能是+1，而不能是-1，只有一種方法使4變成5。可以這樣理解，這里的方法數(shù)量最后是dp[4] * 1，
如果這里1可以是+1也可以是-1的話那方法數(shù)量應(yīng)該是dp[4] * 2

同理，有dp[3]種方法湊成3，現(xiàn)在手上還有一個(gè)2，那么有幾種方法湊成5？還是dp[3]種！

3. dp數(shù)組如何初始化

從遞推公式可以看出，在初始化的時(shí)候dp[0] 一定要初始化為1，因?yàn)閐p[0]是在公式中一切遞推結(jié)果的起源，如果dp[0]是0的話，遞推結(jié)果將都是0。

這里有錄友可能認(rèn)為從dp數(shù)組定義來說 dp[0] 應(yīng)該是0，也有錄友認(rèn)為dp[0]應(yīng)該是1。

其實(shí)不要硬去解釋它的含義，咱就把 dp[0]的情況帶入本題看看應(yīng)該等于多少。

如果數(shù)組[0] ，target = 0，那么 bagSize = (target + sum) / 2 = 0。 dp[0]也應(yīng)該是1， 也就是說給數(shù)組里的元素 0 前面無論放加法還是減法，都是 1 種方法。

所以本題我們應(yīng)該初始化 dp[0] 為 1。

4. 確定遍歷順序

毋庸置疑，對于01背包問題一維dp的遍歷，nums放在外循環(huán)，target在內(nèi)循環(huán)，且內(nèi)循環(huán)倒序。

5. 舉例推導(dǎo)dp數(shù)組

輸入：nums: [1, 1, 1, 1, 1], S: 3

bagSize = (S + sum) / 2 = (3 + 5) / 2 = 4

dp數(shù)組狀態(tài)變化如下：

代碼及詳細(xì)注釋：

一維dp數(shù)組：

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        # 如果nums的和與target的和的奇偶性不同，無法得到目標(biāo)和為target的子集
        if (sum(nums) + target) % 2 == 1:
            return 0
        # 如果目標(biāo)和的絕對值大于nums的和，無法得到目標(biāo)和為target的子集
        if abs(target) > sum(nums):
            return 0
        # 計(jì)算S，S為目標(biāo)和
        S = (target + sum(nums)) // 2
        # 創(chuàng)建一個(gè)長度為S+1的數(shù)組dp，用于記錄可以得到和為i的子集的個(gè)數(shù)
        dp = [0] * (S + 1)
        dp[0] = 1  # 初始化dp[0]為1
        # 遍歷nums中的每個(gè)數(shù)字
        for i in range(len(nums)):
            # 從S到nums[i]遍歷，更新dp數(shù)組
            for j in range(S, nums[i] - 1, -1):
                # 更新dp[j]的值
                dp[j] += dp[j - nums[i]]
        # 返回dp[S]，表示可以得到和為S的子集的個(gè)數(shù)
        return dp[S]

• 時(shí)間復(fù)雜度：O(n × m)，n為正數(shù)個(gè)數(shù)，m為背包容量
• 空間復(fù)雜度：O(m)，m為背包容量

回溯版本：文章來源地址http://www.zghlxwxcb.cn/news/detail-812417.html

class Solution:


    def backtracking(self, candidates, target, total, startIndex, path, result):
        if total == target:
            result.append(path[:])  # 將當(dāng)前路徑的副本添加到結(jié)果中
        # 如果 sum + candidates[i] > target，則停止遍歷
        for i in range(startIndex, len(candidates)):
            if total + candidates[i] > target:
                break
            total += candidates[i]
            path.append(candidates[i])
            self.backtracking(candidates, target, total, i + 1, path, result)
            total -= candidates[i]
            path.pop()

    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total = sum(nums)
        if target > total:
            return 0  # 此時(shí)沒有方案
        if (target + total) % 2 != 0:
            return 0  # 此時(shí)沒有方案，兩個(gè)整數(shù)相加時(shí)要注意數(shù)值溢出的問題
        bagSize = (target + total) // 2  # 轉(zhuǎn)化為組合總和問題，bagSize就是目標(biāo)和

        # 以下是回溯法代碼
        result = []
        nums.sort()  # 需要對nums進(jìn)行排序
        self.backtracking(nums, bagSize, 0, 0, [], result)
        return len(result)

到了這里，關(guān)于力扣：494. 目標(biāo)和（動(dòng)態(tài)規(guī)劃）（01背包）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！