สมมติว่าเรามีรายการตัวเลขที่ไม่เป็นลบที่เรียกว่า nums และยังมีเป้าหมายเป็นจำนวนเต็มด้วย เราต้องหาจำนวนวิธีในการจัดเรียง + และ - เป็นตัวเลข เพื่อให้นิพจน์มีค่าเท่ากับเป้าหมาย
ดังนั้น หากอินพุตเป็น nums =[2, 3, 3, 3, 2] target =9 ผลลัพธ์จะเป็น 2 ดังที่เราสามารถมีได้ -2 + 3 + 3 + 3 + 2 และ 2 + 3 + 3 + 3 – 2.
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:
-
s :=ผลรวมของตัวเลขทั้งหมดเป็น nums
-
ถ้า (s + เป้าหมาย) mod 2 ไม่เหมือนกับ 0 หรือเป้าหมาย> s แล้ว
-
คืนค่า 0
-
-
W :=ผลหารของ (s + เป้าหมาย) / 2
-
dp1 :=รายการขนาด (W + 1) และเติมด้วย 0
-
dp1[0] :=1
-
dp2 :=รายการขนาด (W + 1) และเติมด้วย 0
-
สำหรับฉันในช่วง 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
