步驟一、確定狀態(tài):

確定dp數(shù)組及含義

dp[i]表示的是:裝滿當前的容量j，有多少種裝法?， 存的是方法的數(shù)量

步驟二、推斷狀態(tài)方程:

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

步驟三、規(guī)定初始條件:

初始條件:

全局初始化， 由于都是正整數(shù)，所以可以都初始化0， 而dp數(shù)組初始化的話，dp[0] = 1

步驟四、計算順序:

這個和0-1背包的一致，依然是物品正向遍歷， 背包容量反向遍歷

class Solution:def findTargetSumWays(self, nums: List[int], target: int) -> int:if (target + sum(nums)) % 2 == 1:return 0if (abs(target) > sum(nums)):return 0bagweight = (target + sum(nums)) // 2dp = [0] * (bagweight + 1)dp[0] = 1for i in range(len(nums)):for j in range(bagweight, nums[i]-1, -1):dp[j] = dp[j] + dp[j - nums[i]]return dp[bagweight]

?

《新程序員》：云原生和全面數(shù)字化實踐50位技術專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的96. Leetcode 494. 目标和 (动态规划-背包问题)的全部內容，希望文章能夠幫你解決所遇到的問題。

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