. Jumlah Sasaran

494. Jumlah Sasaran

Kesukaran: Sederhana

Topik: Tatasusunan, Pengaturcaraan Dinamik, Penjejakan Belakang

Anda diberi nombor tatasusunan integer dan sasaran integer.

Anda mahu membina ungkapan daripada nombor dengan menambahkan salah satu simbol ' ' dan '-' sebelum setiap integer dalam nombor dan kemudian menggabungkan semua integer.

• Sebagai contoh, jika nums = [2, 1], anda boleh menambah ' ' sebelum 2 dan '-' sebelum 1 dan menggabungkannya untuk membina ungkapan " 2-1".

Kembalikan bilangan ungkapan berbeza yang boleh anda bina, yang menilai kepada sasaran.

Contoh 1:

• Input: nombor = [1,1,1,1,1], sasaran = 3
• Output: 5
• Penjelasan: Terdapat 5 cara untuk menetapkan simbol untuk menjadikan jumlah nombor menjadi sasaran 3.
  • -1 1 1 1 1 = 3
  • 1 - 1 1 1 1 = 3
  • 1 1 - 1 1 1 = 3
  • 1 1 1 - 1 1 = 3
  • 1 1 1 1 - 1 = 3

Contoh 2:

• Input: angka = [1], sasaran = 1
• Output: 1

Kekangan:

• 1 <= nums.length <= 20
• 0 <= angka[i] <= 1000
• 0 <= jumlah(bilangan[i]) <= 1000
• -1000 <= sasaran <= 1000

Penyelesaian:

Masalah "Jumlah Sasaran" melibatkan mencipta ungkapan menggunakan nombor dalam nombor tatasusunan dengan memberikan tanda atau - pada setiap nombor. Matlamatnya adalah untuk mengira bilangan ungkapan sedemikian yang dinilai kepada sasaran yang diberikan. Masalah ini boleh diselesaikan dengan cekap menggunakan pengaturcaraan dinamik atau menjejak ke belakang.

Perkara Penting

1. Kekangan Input:
   • Panjang tatasusunan: 1 <= nums.length <= 20
   • Nilai elemen: 0 <= nums[i] <= 1000
   • Julat sasaran: -1000 <= sasaran <= 1000

2. Output:

   • Kembalikan kiraan ungkapan yang menilai kepada sasaran.

3. Cabaran:

   • Penyelesaian mesti mengendalikan kedua-dua nilai kecil dan besar sasaran.
   • Pengendalian yang cekap sehingga 2²⁰ kombinasi apabila menggunakan penjejakan belakang.

Pendekatan

Kami boleh menyelesaikan masalah ini menggunakan Pengaturcaraan Dinamik (Transformasi Jumlah Subset) atau Penjejakan Belakang. Di bawah, kami menggunakan Pengaturcaraan Dinamik (DP) untuk kecekapan.

Pemerhatian Utama:

1. Jika kita membahagikan nombor kepada dua kumpulan: P (subset positif) dan N (subset negatif), maka: sasaran = jumlah(P) - jumlah(N)

Susun semula istilah: sum(P) sum(N) = sum(nums)

Biar S menjadi jumlah subset positif. Kemudian: S = (jumlah(bilangan) sasaran) / 2

1. Jika (jumlah(bilangan) sasaran) % 2 ≠ 0, kembalikan 0 kerana mustahil untuk membahagikan jumlah.

Rancang

1. Hitung jumlah keseluruhan nombor.
2. Semak sama ada sasaran boleh dicapai menggunakan formula untuk S . Jika tidak sah, kembalikan 0.
3. Gunakan pendekatan DP untuk mencari kiraan subset dalam nombor yang jumlahnya sama dengan S .

Mari laksanakan penyelesaian ini dalam PHP: 494. Jumlah Sasaran

<?php
/**
 * @param Integer[] $nums
 * @param Integer $target
 * @return Integer
 */
function findTargetSumWays($nums, $target) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$nums = [1, 1, 1, 1, 1];
$target = 3;
echo findTargetSumWays($nums, $target); // Output: 5
?>

Penjelasan:

1. Pengesahan Input:

   • Kami mengira S = (jumlah(bilangan) sasaran) / 2.
   • Jika S bukan integer, adalah mustahil untuk membahagikan nombor kepada dua subset.

2. Logik Pengaturcaraan Dinamik:

   • dp[j] mewakili bilangan cara untuk membentuk jumlah j menggunakan nombor yang diberi.
   • Bermula dengan dp[0] = 1, untuk setiap nombor dalam nombor, kami mengemas kini dp[j] dengan menambah kiraan cara untuk membentuk j - nombor.

3. Keputusan:

   • Selepas memproses semua nombor, dp[S] mengandungi kiraan cara untuk mencapai jumlah sasaran.

Contoh Panduan

Input: nums = [1, 1, 1, 1, 1], sasaran = 3

1. jumlahJumlah = 5, S = (5 3) / 2 = 4.
2. Memulakan tatasusunan DP: dp = [1, 0, 0, 0, 0].
3. Proses setiap nombor:
   • Untuk 1: Kemas kini dp: [1, 1, 0, 0, 0].
   • Untuk 1: Kemas kini dp: [1, 2, 1, 0, 0].
   • Untuk 1: Kemas kini dp: [1, 3, 3, 1, 0].
   • Untuk 1: Kemas kini dp: [1, 4, 6, 4, 1].
   • Untuk 1: Kemas kini dp: [1, 5, 10, 10, 5].
4. Keputusan: dp[4] = 5.

Kerumitan Masa

• Masa: O(n x S), dengan n ialah panjang nombor dan S ialah jumlah sasaran.
• Ruang: O(S) untuk tatasusunan DP.

Output sebagai Contoh

Input: nums = [1,1,1,1,1], sasaran = 3

Output: 5

Pendekatan ini secara cekap mengira bilangan cara untuk membentuk jumlah sasaran menggunakan pengaturcaraan dinamik. Dengan mengurangkan masalah kepada jumlah subset, kami memanfaatkan struktur DP untuk prestasi yang lebih baik.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:

• LinkedIn
• GitHub

Atas ialah kandungan terperinci . Jumlah Sasaran. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!