。目标总和
Jan 02, 2025 pm 05:38 PM494。目标金额
难度:中等
主题:数组、动态规划、回溯
给你一个整数数组 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
-
输出:
- 返回计算结果为目标的表达式的计数。
-
挑战:
- 解决方案必须同时处理较小和较大的目标值。
- 使用回溯时有效处理多达 220 个组合。
接近
我们可以使用动态规划(子集和变换)或回溯来解决这个问题。下面,我们使用动态规划(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。目标金额
<?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 ?>
解释:
-
输入验证:
- 我们计算 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。
时间复杂度
- 时间:O(n x S),其中n是nums的长度,S是目标总和。
- 空格:DP 数组的 O(S)。
示例输出
输入: nums = [1,1,1,1,1], target = 3
输出:5
这种方法使用动态规划有效地计算形成目标总和的方法数量。通过将问题简化为子集和,我们利用 DP 的结构来获得更好的性能。
联系链接
如果您发现本系列有帮助,请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子?。您的支持对我来说意义重大!
如果您想要更多类似的有用内容,请随时关注我:
- 领英
- GitHub
以上是。目标总和的详细内容。更多信息请关注PHP中文网其他相关文章!

热门文章

热门文章

热门文章标签

记事本++7.3.1
好用且免费的代码编辑器

SublimeText3汉化版
中文版,非常好用

禅工作室 13.0.1
功能强大的PHP集成开发环境

Dreamweaver CS6
视觉化网页开发工具

SublimeText3 Mac版
神级代码编辑软件(SublimeText3)