Jumlah Sasaran dengan Tanda Positif dan Negatif
Tukarkan masalah penetapan jumlah sasaran kepada beg galas berdasarkan perbezaan jumlah subset, dan selesaikannya dalam masa O(n × sum).
Jumlah Sasaran dengan Tanda Positif dan Negatif ialah pelajaran DSA Interview Prep percuma di CoddyKit. Ini ialah pelajaran 4 daripada 4. Sebanyak 3 pelajaran dalam laluan pembelajaran ini boleh dibaca sepenuhnya secara percuma — selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan praktikal dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran DSA Interview Prep, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus DSA Interview Prep merangkumi sejumlah 4 pelajaran.
Masalah Jumlah Sasaran
Diberi tatasusunan integer nums dan integer target, berikan tanda + atau - kepada setiap nombor supaya ungkapan yang terhasil dinilai kepada target. Pulangkan bilangan cara berbeza untuk melakukannya. Contohnya, dengan nums=[1,1,1,1,1] dan target=3, terdapat 5 cara (pilih 4 elemen untuk menjadi positif dan 1 elemen untuk menjadi negatif pada kedudukan yang berbeza).
Carian Menyeluruh: Penghitungan DFS
Pendekatan DFS memberikan setiap nombor sama ada tanda + atau - dan memanggil dirinya secara rekursif, lalu memulangkan bilangan nod daun yang mencapai target. Pendekatan ini betul tetapi mempunyai kerumitan masa O(2^n) — eksponen. Apabila n=20, ini menghasilkan lebih daripada sejuta panggilan rekursif. Pendekatan DFS wajar disebut terlebih dahulu, kemudian segera beralih kepada pengoptimuman DP.
def findTargetSumWays_dfs(nums, target):
count = [0]
def dfs(i, current_sum):
if i == len(nums):
if current_sum == target:
count[0] += 1
return
dfs(i+1, current_sum + nums[i])
dfs(i+1, current_sum - nums[i])
dfs(0, 0)
return count[0]
print(findTargetSumWays_dfs([1,1,1,1,1], 3)) # 5DFS dengan Memoisasi
Tambahkan memoization kepada DFS: keadaannya ialah (index, current_sum). Oleh sebab current_sum boleh berjulat daripada -total hingga +total, terdapat O(n × total) keadaan unik. Dengan memoization, DFS berjalan dalam masa dan ruang O(n × total). Pendekatan ini berfungsi dan sah dalam temu duga, tetapi DP berasaskan transformasi lebih anggun serta lebih cekap dari segi ruang.
from functools import lru_cache
def findTargetSumWays_memo(nums, target):
total = sum(nums)
@lru_cache(maxsize=None)
def dp(i, remaining):
if i == len(nums):
return 1 if remaining == 0 else 0
return dp(i+1, remaining - nums[i]) + dp(i+1, remaining + nums[i])
return dp(0, target)
print(findTargetSumWays_memo([1,1,1,1,1], 3)) # 5Transformasi Matematik
Biarkan P ialah himpunan nombor yang diberikan tanda + dan N ialah himpunan yang diberikan tanda -. Maka: sum(P) - sum(N) = target dan sum(P) + sum(N) = total. Dengan menjumlahkan kedua-duanya: 2 × sum(P) = target + total, maka sum(P) = (target + total) / 2. Masalah ini dikurangkan kepada: mengira subhimpunan nums yang berjumlah (target + total) / 2. Ini tepat-tepat ialah varian mengira subhimpunan bagi masalah beg galas 0/1.
# sum(P) - sum(N) = target
# sum(P) + sum(N) = total
# => 2*sum(P) = target + total
# => sum(P) = (target + total) / 2
# Count subsets with sum = new_target = (target + total) // 2
print('Reduction: count subsets summing to (target + total) // 2')Semakan Kesahan Sebelum DP
Sebelum menjalankan DP, semak perkara berikut: (1) target + total mestilah genap (jika tidak, sum(P) bukan integer — mustahil); (2) abs(target) > total bermaksud sasaran tidak boleh dicapai walaupun semua tanda selaras. Jika mana-mana semakan gagal, segera pulangkan 0. Semakan ini mengendalikan kes tepi dengan kemas tanpa memerlukan pengendalian kes khas dalam gelung DP.
def findTargetSumWays(nums, target):
total = sum(nums)
if (target + total) % 2 != 0:
return 0 # sum(P) would be non-integer
if abs(target) > total:
return 0 # impossible to reach
new_target = (target + total) // 2
# Count subsets summing to new_target
dp = [0] * (new_target + 1)
dp[0] = 1
for num in nums:
for c in range(new_target, num - 1, -1):
dp[c] += dp[c - num]
return dp[new_target]
print(findTargetSumWays([1,1,1,1,1], 3)) # 5Menelusuri Contoh Kecil
Bagi nums=[1,1,1,1,1], target=3: jumlah keseluruhan=5, new_target=(3+5)//2=4. Kita mengira subhimpunan yang berjumlah 4 daripada [1,1,1,1,1]. Ini ialah C(5,4)=5 (pilih 4 angka satu untuk menjadi positif, manakala angka satu yang kelima menjadi negatif: 1+1+1+1-1=3). DP memulangkan 5 dengan betul. Transformasi ini memetakan masalah penetapan tanda kepada masalah pengiraan subhimpunan yang standard dengan elegan.
Mengendalikan Sifar dalam Tatasusunan Nombor
Jika nums mengandungi sifar, memberikan tanda + atau - kepada sifar tidak mengubah jumlah. Setiap sifar menggandakan bilangan penetapan yang sah. DP mengendalikan perkara ini secara semula jadi: apabila memproses num=0, gelung dalaman range(new_target, -1, -1) berjalan daripada new_target turun hingga 0, dan dp[c] += dp[c - 0] = dp[c] menggandakan semua jumlah yang boleh dicapai. Tiada pengendalian khas diperlukan jika anda menggunakan range(new_target, num-1, -1), yang bermula daripada new_target dan turun hingga 0 apabila num=0.
# With zeros: each zero doubles the count
print(findTargetSumWays([0, 0, 1], 1)) # 4
# Assignments: +0+0+1, +0-0+1, -0+0+1, -0-0+1 = all give sum 1Perbandingan Kerumitan
DFS carian menyeluruh ialah O(2^n). DFS bermemoisasi ialah masa O(n × total) dan ruang O(n × total). DP 1D berasaskan transformasi ialah masa O(n × new_target) dan ruang O(new_target), dengan new_target ≤ total. DP 1D menggunakan ruang yang jauh lebih kecil berbanding memoization kerana membuang dimensi indeks melalui transformasi.
Hubungan dengan Masalah Beg Galas Lain
Jumlah Sasaran menghubungkan beberapa konsep masalah beg galas: ia bermula sebagai masalah penetapan, berubah menjadi jumlah subhimpunan (seperti Pembahagian Jumlah Subhimpunan Sama Rata), dan menggunakan templat lelaran mengundur masalah beg galas 0/1 yang sama tetapi dengan pengiraan (seperti Pertukaran Syiling II). Menguasai hubungan ini membolehkan anda mengelaskan masalah baharu dengan cepat dalam temu duga berdasarkan persamaan strukturnya dengan corak yang telah diketahui.
Kes Tepi dan Nota Temu Duga
Kes utama: (1) target = total: hanya satu cara (semuanya positif); (2) target = -total: hanya satu cara (semuanya negatif); (3) target = 0 dengan semua elemen sifar: jawapannya ialah 2^n; (4) jumlah keseluruhan yang sangat besar tetapi n kecil — saiz tatasusunan DP 1D dihadkan oleh total/2. Dalam temu duga, terangkan langkah transformasi secara lisan sebelum menulis kod — ini ialah pandangan penting yang tidak jelas dan membezakan calon yang kukuh.
Alternatif DP 2D Tanpa Transformasi
Tanpa transformasi, takrifkan dp[i][s] = bilangan cara memberikan tanda kepada i nombor pertama untuk mencapai jumlah s. Jumlah boleh menjadi negatif, jadi gunakan anjakan sebanyak total: gunakan dp[i][s + total]. Ini memerlukan jadual 2D bersaiz (n+1) × (2*total+1). Walaupun betul, pendekatan ini menggunakan lebih banyak ruang dan lebih sukar ditulis dengan cepat di bawah tekanan temu duga berbanding beg galas 1D selepas transformasi.
Semakan Pantas
Uji pemahaman anda tentang konsep Struktur Data & Algoritma — Persediaan Temu Duga Pengekodan daripada pelajaran ini.
Ulang Kaji Pelajaran
Dalam pelajaran ini, anda mempelajari bahawa: Jumlah Sasaran menukarkan penetapan tanda kepada pengiraan subhimpunan yang berjumlah (target + total) / 2, lelaran mengundur masalah beg galas 0/1 1D mengira subhimpunan dalam masa O(n × new_target) dan ruang O(new_target), dan semakan kesahan awal (jumlah ganjil, |target| > total) mengelakkan pelaksanaan DP yang tidak perlu. Seterusnya, kita beralih kepada bidang laluan terpendek dengan algoritma Dijkstra dan baris gilir keutamaan.
Pelajari Python dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 30
- Pelajaran
- 120
Soalan Lazim
Adakah pelajaran “Jumlah Sasaran dengan Tanda Positif dan Negatif” percuma?
Ya — sebanyak 3 pelajaran dalam laluan pembelajaran DSA Interview Prep, termasuk “Jumlah Sasaran dengan Tanda Positif dan Negatif”, boleh dibaca sepenuhnya secara percuma di web ini. Selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan interaktif dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Kursus DSA Interview Prep merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Jumlah Sasaran dengan Tanda Positif dan Negatif”?
Tukarkan masalah penetapan jumlah sasaran kepada beg galas berdasarkan perbezaan jumlah subset, dan selesaikannya dalam masa O(n × sum). Anda berlatih DSA Interview Prep menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan DSA Interview Prep?
Tiada pengalaman terdahulu diperlukan. Pembelajaran DSA Interview Prep di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 4 daripada 4.
Berapa lamakah pelajaran “Jumlah Sasaran dengan Tanda Positif dan Negatif” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran DSA Interview Prep ini?
Ya. Setiap pelajaran DSA Interview Prep menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- Beg Galas 0/1 dan Pengoptimuman Ruang
- Beg Galas Tanpa Had dan Pertukaran Syiling II
- Jumlah Subset Sama bagi Pembahagian
- Jumlah Sasaran dengan Tanda Positif dan Negatif