image.png

思考

由于數組和不超過1000，考慮到k有可能是負數，統(tǒng)計加上1000防止值為負導致越界
但是這樣仍然可能越界 需要再處理邊界
D:dp[i][k]=n 表示包括nums[i]能組成和為k的種數為n 得把和求出來
T:dp[i][k] = dp[i-1][k-nums[i]] + dp[i-1][k+nums[i]]
B: 只有第一個元素時 dp[0][1000-nums[0]] +=1 dp[0][1000+nums[0]] +=1

實現

class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
       
        if not nums:
            return 0
        nums_len = len(nums)
        nums_sum = sum(nums)
        if S>nums_sum or S<-nums_sum or (S+nums_sum)%2!=0:
            return 0
        dp = [[0]*(2*1000+1) for _ in range(nums_len)] 
        dp[0][1000-nums[0]] +=1
        dp[0][1000+nums[0]] +=1
        for i in range(1,nums_len):
            for j in range(-nums_sum,nums_sum+1):
                p = dp[i-1][j+nums[i]+1000] if j+nums[i]+1000<2*1000+1 else 0
                n = dp[i-1][j-nums[i]+1000] if j-nums[i]+1000>=0 else 0
                dp[i][j+1000]=n+p
        return dp[nums_len-1][S+1000]

反思

由于dp[i][k]只依賴上一個狀態(tài)，可以考慮用一維的滾動數組進行狀態(tài)壓縮，我們發(fā)現 dp和上一行的左右倆邊都可能有關系 無論正向還是逆向遍歷，都會導致nums[i]重復產生影響，我們可以用一個臨時數組來保持當前i的計算結果，i全部計算完成再更新掉原來的dp

實現

class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        if not nums:
            return 0
        nums_len = len(nums)
        nums_sum = sum(nums)
        if S>nums_sum or S<-nums_sum or (S+nums_sum)%2!=0:
            return 0
        dp = [0]*(2*nums_sum+1) # 表示-sum到sum
        dp[nums_sum-nums[0]] +=1 # 注意初始是0 時的情況 這里得用加法進行更新
        dp[nums_sum+nums[0]] +=1
        for i in range(1,nums_len):
            next_ = [0]*(2*nums_sum+1)
            for j in range(-nums_sum,nums_sum+1):
                p = dp[j+nums[i]+nums_sum] if 0<=j+nums[i]+nums_sum<2*nums_sum+1 else 0
                n = dp[j-nums[i]+nums_sum] if 0<=j-nums[i]+nums_sum<2*nums_sum+1 else 0
                next_[j+nums_sum]=n+p
            dp=next_
        return dp[S+nums_sum]

再優(yōu)化

由于加法具有交換律，我們可以把加正號得數放在一起構成一個子集 P ，加負號的放在一起構成子集N，問題就變成了分割成倆分子集使得P-N=target
我們知道 P+N=sum(nums) 兩式相加 2P = target+sum(nums) 問題就變成了求 和為 (target+sum(nums))/2的一個子集有多少個 這是一個典型的0-1背包問題
剪枝 由公式可知 target+sum(nums)得是偶數
還可以運用0-1背包的空間優(yōu)化法

實現

class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        if sum(nums) < S or (sum(nums) + S) % 2 == 1: return 0
        P = (sum(nums) + S) // 2
        dp = [1] + [0 for _ in range(P)] # 和為0的子集說明什么都不選
        for i in range(len(nums)):
            for j in range(P,-1,-1):
                dp[j] = dp[j]+dp[j-nums[i]] if j-nums[i]>=0 else dp[j] # 0-1背包 j代表容量 dp[j]=k 代表容量為j時的拿法有k種
        return dp[P]