- 博客主頁：誓則盟約
- 系列專欄：IT競賽 專欄
- 關注博主，后期持續更新系列文章
- 如果有錯誤感謝請大家批評指出，及時修改
- 感謝大家點贊👍收藏?評論??
494.目標和【中等】
題目：
給你一個非負整數數組?nums?和一個整數?target?。
向數組中的每個整數前添加?'+'?或?'-'?，然后串聯起所有整數，可以構造一個?表達式?：
- 例如，
nums = [2, 1]?，可以在?2?之前添加?'+'?，在?1?之前添加?'-'?，然后串聯起來得到表達式?"+2-1"?。
返回可以通過上述方法構造的、運算結果等于?target?的不同?表達式?的數目。
示例 1：
輸入：nums = [1,1,1,1,1], target = 3 輸出：5 解釋：一共有 5 種方法讓最終目標和為 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 <= 200 <= nums[i] <= 10000 <= sum(nums[i]) <= 1000-1000 <= target <= 1000
分析問題：
設?nums?的元素和為?s，添加正號的元素之和為?p，添加負號的元素（絕對值）之和為?q，那么有
- p+q=s
- p-q=target
化簡得：
- p = (s+target) / 2?
- q = (s-target) / 2
? ? ? ? 我們找所有元素里面選取出來的元素和恰好為p的方案個數，那么這就變成了一道經典的0-1背包問題的變形，找恰好裝capacity,求方案數/最大/最小價值和，capacity指的是容量，也就是這里的負數的和的絕對值。
????????那么我們就可以根據傳統的0-1背包問題的求解過程來解題，帶上cache數組以便達到記憶化的一個效果。
????????此處也可以進行進一步的優化，用一個二維數組f來替代遞推函數dfs：
????????首先創建一個二維數組f，其中n表示數組的長度，target表示目標值，該數組用于記錄不同狀態下的結果。
????????然后將f[0][0]初始化為1，這是一個基礎的起始條件。接下來通過兩個嵌套循環進行計算。外層循環遍歷一個名為nums的數組，其中的每個元素x代表物品的價值。內層循環遍歷目標值target的所有可能取值。在循環內部，根據不同條件更新f數組的值。
- ????????如果c小于x，說明當前考慮的物品價值x大于當前的目標值c，無法選擇該物品，所以f[i + 1][c]保持與f[i][c]相同。
- ????????如果c大于或等于x，那么f[i + 1][c]等于f[i][c]加上f[i][c - x]，這表示在這種情況下，可以選擇該物品，所以要將不選擇該物品的情況（f[i][c]）和選擇該物品的情況（f[i][c - x]）的結果相加。
????????最后，函數返回f[n][target]，即最終在考慮了所有物品和目標值的情況下的結果。
代碼實現：
優化前：
class Solution:def findTargetSumWays(self, nums: list[int], target: int) -> int:# p = (s+t) /2target += sum(nums)if target < 0 or target % 2:return 0target //=2n=len(nums)@cache # 保存記憶def dfs(i,c): # i是剩余多少個物品沒裝 c是當前背包剩余容量if i<0:return 1 if c==0 else 0if c < nums[i]:return dfs(i-1,c)return dfs(i-1,c)+dfs(i-1,c-nums[i])return dfs(n-1,target)
?
優化后:
class Solution:def findTargetSumWays(self, nums: list[int], target: int) -> int:# p = (s+t) /2target += sum(nums)if target < 0 or target % 2:return 0target //=2n=len(nums)f=[[0]*(target+1) for _ in range(n+1)]f[0][0]=1for i,x in enumerate(nums):for c in range(target+1):if c<x: f[i+1][c] = f[i][c]else: f[i+1][c] = f[i][c] + f[i][c-x]return f[n][target]
?
總結：
優化后代碼詳細解釋：
target += sum(nums)：將target值加上數組nums的元素總和，得到p的2倍。if target < 0 or target % 2:：檢查新的target值是否小于0或是否為奇數。如果是，則直接返回0，表示無法得到目標值。target //= 2：將target值除以2，得到用于后續計算的新值。n = len(nums)：獲取數組nums的長度。f = [[0] * (target + 1) for _ in range(n + 1)]：創建一個二維數組f，用于動態規劃的計算。f[0][0] = 1：設置初始狀態，即當沒有元素且目標值為0時，有一種方法可以達到。- 通過兩個嵌套循環進行動態規劃計算：
- 外層循環
for i, x in enumerate(nums):遍歷數組nums的每個元素。 - 內層循環
for c in range(target + 1):遍歷所有可能的目標值。 - 在循環內部，根據當前元素
x和目標值c的關系更新f[i + 1][c]的值。如果c < x，則f[i + 1][c] = f[i][c]，表示無法選擇當前元素來達到目標值；如果c >= x，則f[i + 1][c] = f[i][c] + f[i][c - x]，表示可以選擇或不選擇當前元素來達到目標值，將兩種情況的方法數相加。
- 外層循環
- 最后，函數返回
f[n][target]，即使用整個數組nums達到最終目標值的方法數。
考點：
- 動態規劃的應用：通過構建二維數組來記錄不同狀態下的結果，根據狀態轉移方程進行計算。
- 對問題的數學轉化：將原問題轉化為通過加減運算得到特定值的問題，并進行了一些預處理和條件判斷。
收獲：
- 深入理解了動態規劃的思想和應用方法，學會如何根據問題的特點構建合適的狀態和狀態轉移方程。
- 提高了對問題進行數學分析和轉化的能力，能夠將復雜的問題簡化為可計算的形式。
- 增強了對數組操作和循環的熟練程度，能夠靈活運用這些基本編程技巧來解決實際問題。
)
)
