。目标总和

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中文网其他相关文章！