資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python程式：如何找到排列符號以獲得目標結果的方法數量？
假設我們有一個稱為 nums 的非負數列表，還有一個整數目標值 target。我們需要找到在 nums 中排列 + 和 - 的方法數量，使得表示式等於目標值。
因此，如果輸入類似於 nums = [2, 3, 3, 3, 2] target = 9，則輸出將為 2，因為我們可以有 -2 + 3 + 3 + 3 + 2 和 2 + 3 + 3 + 3 – 2。
為了解決這個問題，我們將遵循以下步驟
s := nums 中所有數字的總和
如果 (s + target) mod 2 與 0 不相同或 target > s，則
返回 0
W := (s + target) / 2 的商
dp1 := 大小為 (W + 1) 的列表，並填充 0
dp1[0] := 1
dp2 := 大小為 (W + 1) 的列表，並填充 0
對於 i 從 0 到 nums 的大小，執行
對於 j 從 0 到 W + 1，執行
如果 j >= nums[i]，則
dp2[j] := dp2[j] + dp1[j - nums[i]]
對於 j 從 0 到 W + 1，執行
dp1[j] := dp1[j] + dp2[j]
dp2[j] := 0
返回 dp1 的最後一個元素
讓我們看看以下實現以獲得更好的理解
示例
class Solution: def solve(self, nums, target): s = sum(nums) if (s + target) % 2 != 0 or target > s: return 0 W = (s + target) // 2 dp1 = [0] * (W + 1) dp1[0] = 1 dp2 = [0] * (W + 1) for i in range(len(nums)): for j in range(W + 1): if j >= nums[i]: dp2[j] += dp1[j - nums[i]] for j in range(W + 1): dp1[j] += dp2[j] dp2[j] = 0 return dp1[-1] ob = Solution() nums = [2, 3, 3, 3, 2] target = 9 print(ob.solve(nums, target))
輸入
[2, 3, 3, 3, 2], 9
輸出
2
更新於: 2020年11月10日
114 次檢視
廣告