。目標總和

494。目標金額

難度：中

主題：陣列、動態規劃、回溯

給你一個整數陣列 nums 和一個整數目標。

您想要透過在 nums 中的每個整數之前加上符號 ' ' 和 '-' 之一，然後連接所有整數來建立 nums 中的 表達式。

• 例如，如果 nums = [2, 1]，您可以在 2 之前加上“ ”，在 1 之前加上“-”，並將它們連接起來建立表達式“ 2-1”。

傳回您可以建立的不同表達式的數量，其計算結果為目標。

範例1：

• 輸入： nums = [1,1,1,1,1], target = 3
• 輸出： 5
• 說明：有 5 種分配符號的方法，使 nums 的總和為目標 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

範例2：

• 輸入： nums = [1]，目標 = 1
• 輸出： 1

約束：

• 1
• 0
• 0
• -1000

解：

「目標和」問題涉及透過為每個數字分配一個或 - 符號，使用數組 nums 中的數字建立表達式。目標是計算有多少個此類表達式計算結果為給定目標。這個問題可以使用動態規劃或回溯來有效解決。

要點

1. 輸入約束：
   • 陣列長度：1
   • 元素值：0
   • 目標範圍：-1000

2. 輸出:

   • 傳回計算結果為目標的表達式的計數。

3. 挑戰：

   • 解決方案必須同時處理較小和較大的目標值。
   • 使用回溯時有效處理多達 2²⁰ 個組合。

接近

我們可以用動態規劃（子集和變換）或回溯來解決這個問題。下面，我們使用動態規劃（DP）來提高效率。

主要觀察結果：

1. 如果我們將 nums 分成兩組：P（正子集）和 N（負子集），則： target = sum(P) - sum(N)

重新排列項： sum(P) sum(N) = sum(nums)

設 S 為正子集的總和。然後：S = (sum(nums) 目標) / 2

1. 如果 (sum(nums) target) % 2 ≠ 0，則傳回 0，因為無法對總和進行分區。

計畫

1. 計算 nums 的總和。
2. 使用 S 公式檢查目標是否可以實現。如果無效，則回傳0。
3. 使用 DP 方法找出 nums 中總和等於 S .
的子集的數量

讓我們用 PHP 實作這個解：494。目標金額

<?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
?>

解釋：

1. 輸入驗證:

   • 我們計算 S = (sum(nums) target) / 2.
   • 如果 S 不是整數，則不可能將 nums 分成兩個子集。

2. 動態程式邏輯:

   • dp[j] 表示使用給定數字形成和 j 的方法的數量。
   • 從 dp[0] = 1 開始，對於 nums 中的每個數字，我們透過添加形成 j - num 的方式計數來更新 dp[j]。

3. 結果：

   • 處理完所有數字後，dp[S]包含達到目標總和的方法數。

範例演練

輸入: nums = [1, 1, 1, 1, 1], target = 3

1. 總和 = 5，S = (5 3) / 2 = 4.
2. 初始化 DP 陣列：dp = [1, 0, 0, 0, 0].
3. 處理每個數字：
   • 對於 1：更新 dp：[1, 1, 0, 0, 0]。
   • 對於 1：更新 dp：[1, 2, 1, 0, 0]。
   • 對於 1：更新 dp：[1, 3, 3, 1, 0]。
   • 對於 1：更新 dp：[1, 4, 6, 4, 1]。
   • 對於 1：更新 dp：[1, 5, 10, 10, 5]。
4. 結果：dp[4] = 5。

時間複雜度

• 時間：O(n x S)，其中n是nums的長度，S是目標總和。
• 空格：DP 陣列的 O(S)。

範例輸出

輸入: nums = [1,1,1,1,1], target = 3

輸出：5

這種方法使用動態規劃有效地計算形成目標總和的方法數量。透過將問題簡化為子集和，我們利用 DP 的結構來獲得更好的效能。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是。目標總和的詳細內容。更多資訊請關注PHP中文網其他相關文章！