。目标总和-php教程-PHP中文网

首页

后端开发

php教程

。目标总和

Jan 02, 2025 pm 05:38 PM

. Target Sum

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
- 元素值：0
- 目标范围：-1000
输出:
- 返回计算结果为目标的表达式的计数。
挑战：
- 解决方案必须同时处理较小和较大的目标值。
- 使用回溯时有效处理多达 2²⁰ 个组合。

接近

我们可以使用动态规划（子集和变换）或回溯来解决这个问题。下面，我们使用动态规划（DP）来提高效率。

主要观察结果：

如果我们将 nums 分为两组：P（正子集）和 N（负子集），则： target = sum(P) - sum(N)

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

令 S 为正子集的总和。然后：S<sub> = (sum(nums) 目标) / 2

如果 (sum(nums) target) % 2 ≠ 0，则返回 0，因为无法对总和进行分区。

计划

计算 nums 的总和。
使用 S 公式检查目标是否可以实现。如果无效，返回0。
使用 DP 方法查找 nums 中总和等于 S.

让我们用 PHP 实现这个解决方案：494。目标金额

&lt;?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
?&gt;

登录后复制

解释：

输入验证:
- 我们计算 S = (sum(nums) target) / 2.
- 如果 S 不是整数，则不可能将 nums 分成两个子集。
动态编程逻辑:
- dp[j] 表示使用给定数字形成和 j 的方法的数量。
- 从 dp[0] = 1 开始，对于 nums 中的每个数字，我们通过添加形成 j - num 的方式计数来更新 dp[j]。
结果：
- 处理完所有数字后，dp[S]包含达到目标总和的方法数。

示例演练

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

总和 = 5，S = (5 3) / 2 = 4.
初始化 DP 数组：dp = [1, 0, 0, 0, 0].
处理每个数字：
- 对于 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]。
结果：dp[4] = 5。