LeetCode 494 目标和：从动态规划到零钱兑换问题的深度剖析

内容摘要：LeetCode 494 目标和：从动态规划到零钱兑换问题的深度剖析,

在 LeetCode 刷题过程中， leetcode 494 目标和 是一道经典的动态规划问题，它考察了我们对于状态转移方程的理解和应用。这道题的本质可以看作是带符号的子集划分问题，求解有多少种给定的数组元素分配正负号的方式，使得最终的和等于目标值 target。

问题场景重现：目标和的本质

给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 - 中选择一个符号添加在前面。求出有多少种添加符号的方法可以使最终的和为 S。

例如，数组 nums = [1, 1, 1, 1, 1], target = 3. 共有 5 种方法让和为 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)

底层原理深度剖析：从背包问题到状态转移

目标和问题可以通过转换为背包问题来解决。假设数组中所有正数的和为 positive_sum，所有负数的绝对值和为 negative_sum，那么 positive_sum - negative_sum = target。同时，positive_sum + negative_sum = sum(nums)。两式相加，可得 positive_sum = (target + sum(nums)) / 2。因此，问题转化为：从 nums 中选取若干个数，使得它们的和等于 positive_sum，求有多少种选法。 这就是一个经典的 0-1 背包问题。

假设 dp[i][j] 表示从数组 nums 的前 i 个数中选取若干个数，使得它们的和等于 j 的方案数。状态转移方程如下：

• 如果 nums[i-1] > j：dp[i][j] = dp[i-1][j]
• 如果 nums[i-1] <= j：dp[i][j] = dp[i-1][j] + dp[i-1][j - nums[i-1]]

其中，dp[i-1][j] 表示不选第 i 个数，dp[i-1][j - nums[i-1]] 表示选第 i 个数。

代码实现（Java）

public class TargetSum {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        // 如果 target 的绝对值大于 sum，则不可能存在方案
        if (Math.abs(target) > sum) {
            return 0;
        }

        // 如果 (target + sum) 不是偶数，则不可能存在方案
        if ((target + sum) % 2 != 0) {
            return 0;
        }

        int positive_sum = (target + sum) / 2;

        // dp[i][j] 表示从 nums 的前 i 个数中选取若干个数，使得它们的和等于 j 的方案数
        int[][] dp = new int[nums.length + 1][positive_sum + 1];
        dp[0][0] = 1; // 初始化：不选任何数，和为 0 的方案数为 1

        for (int i = 1; i <= nums.length; i++) {
            for (int j = 0; j <= positive_sum; j++) {
                if (nums[i - 1] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]];
                }
            }
        }

        return dp[nums.length][positive_sum];
    }

    public static void main(String[] args) {
        TargetSum solution = new TargetSum();
        int[] nums = {1, 1, 1, 1, 1};
        int target = 3;
        int result = solution.findTargetSumWays(nums, target);
        System.out.println("Number of ways: " + result); // 输出：5
    }
}

空间优化：一维 DP 数组

观察上述代码，可以发现 dp[i][j] 的值只依赖于 dp[i-1][j] 和 dp[i-1][j - nums[i-1]]。因此，可以使用一维 DP 数组来优化空间复杂度。

public int findTargetSumWaysOptimized(int[] nums, int target) {
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }

    if (Math.abs(target) > sum || (sum + target) % 2 != 0) {
        return 0;
    }

    int positive_sum = (sum + target) / 2;
    int[] dp = new int[positive_sum + 1];
    dp[0] = 1;

    for (int num : nums) {
        for (int j = positive_sum; j >= num; j--) {
            dp[j] += dp[j - num];
        }
    }
    return dp[positive_sum];
}

注意：内层循环必须从 positive_sum 递减到 num，以防止重复计算。

实战避坑经验总结

1. 边界条件处理：一定要注意 target 的绝对值大于 sum，以及 (target + sum) 不是偶数的情况。这两种情况下，都不可能存在解决方案，直接返回 0。
2. 正负数和的计算：务必保证 positive_sum 的计算准确无误，它直接影响 DP 数组的大小和最终结果。
3. 空间优化方向：理解一维 DP 数组优化的原理，确保内层循环的方向正确，避免重复计算导致结果错误。
4. 测试用例全面性：除了题目给出的示例，需要考虑各种特殊情况，例如数组全为 0，数组长度为 1 等情况。
5. 关注性能：在面对大规模数据时，需要考虑时间和空间复杂度。空间优化可以显著提升性能。 可以结合实际场景考虑使用 Nginx 进行流量代理，通过反向代理和负载均衡将请求分发到多台服务器上，提高系统的并发连接数，避免单点故障。可以使用宝塔面板快速搭建和管理 Nginx 服务。

通过对 leetcode 494 目标和 问题的深入分析和代码实现，我们可以更好地掌握动态规划算法，并将其应用到其他类似的问题中。理解问题本质，优化代码，并不断积累实战经验，是成为一名优秀的后端架构师的关键。