494. 目标和

Powered by:NEFU AB-IN

Link

494. 目标和

• 题意

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

• 思路

1. 正常dfs

   1. 需要注意：
      1. nonlocal cnt ，使用 nonlocal 来引用外部的 cnt，在函数嵌套是用这个。在函数和全局变量时，用global
      2. 不需要像全排列一样，用个for i in range(n):，去遍历未使用的元素，用了for循环加入未被选的元素，实际上更改了相对位置，其实就相当于把顺序也考虑上了，相当于排列，而不是组合。所以在这里每个元素都有固定的位置，并且每个位置都有两种选择（+ 或 -），不需要使用 for 循环来遍历可能的选择

2. dp背包问题（复杂版）

   1. 定义一个二维数组 dp[i][j]，其中 i 表示处理到第 i 个数字，j 表示当前的和，dp[i][j] 表示能够达到和 j 的不同表达式的数目。
      1. $dp[i][j]=dp[i-1][j-nums[i]]+dp[i-1][j+nums[i]]$
      2. 不能从大到小更新，因为涉及两个数的改变
   2. 优化为一维数组 dp，其中 dp[j] 表示和为 j 的表达式的个数。（因为dp[i]只和dp[i-1]有关，为滚动数组优化）
      1. 当前的状态只和前一个状态有关。
      2. 更新当前状态时，我们可以从后向前遍历来避免覆盖问题。

3. dp背包问题（简单版）

   1. 简化问题：找到所有子集，使得这些子集的和等于 (sum(nums) - target) / 2 或者 (sum(nums) + target) / 2，这两个等价

      具体步骤如下：

   • 计算数组 nums 的总和 sum(nums)。如果 (sum(nums) - target) 不是偶数，那么无法得到整数的目标值，直接返回 0。
   • 定义 DP 数组 dp，其中 dp[j] 表示和为 j 的不同表达式的数目。
   • 初始化 dp[0] = 1，因为和为 0 的情况是一个合法的表达式。
   • 遍历数组 nums，对于每一个数，从背包容量（即目标值）开始，向下遍历，更新 dp 数组。
   • 最终 dp[(sum(nums) - target) / 2] 的值就是所求结果。

• 代码

'''
Author: NEFU AB-IN
Date: 2024-06-30 21:25:56
FilePath: \LeetCode\494\494.py
LastEditTime: 2024-07-01 19:58:59
'''
# 3.8.19 import
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, fabs, floor, gcd, log, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin, stdout
from typing import Any, Dict, Generic, List, TypeVar, Union

TYPE = TypeVar('TYPE')

# Data structure
class SA(Generic[TYPE]):
    def __init__(self, x: TYPE, y: TYPE):
        self.x = x
        self.y = y

    def __lt__(self, other: 'SA[TYPE]') -> bool:
        return self.x < other.x

    def __eq__(self, other: 'SA[TYPE]') -> bool:
        return self.x == other.x and self.y == other.y

    def __repr__(self) -> str:
        return f'SA(x={self.x}, y={self.y})'


# Constants
N = int(2e5 + 10)  # If using AR, modify accordingly
M = int(20)  # If using AR, modify accordingly
INF = int(2e9)
OFFSET = int(100)

# Set recursion limit
setrecursionlimit(INF)

# Read
def input(): return stdin.readline().rstrip("\r\n")  # Remove when Mutiple data
def read(): return map(int, input().split())
def read_list(): return list(read())


# Func
class std:
    letter_to_num = staticmethod(lambda x: ord(x.upper()) - 65)  # A -> 0
    num_to_letter = staticmethod(lambda x: ascii_uppercase[x])  # 0 -> A
    array = staticmethod(lambda x=0, size=N: [x] * size)
    array2d = staticmethod(lambda x=0, rows=N, cols=M: [std.array(x, cols) for _ in range(rows)])
    max = staticmethod(lambda a, b: a if a > b else b)
    min = staticmethod(lambda a, b: a if a < b else b)
    removeprefix = staticmethod(lambda s, prefix: s[len(prefix):] if s.startswith(prefix) else s)
    removesuffix = staticmethod(lambda s, suffix: s[:-len(suffix)] if s.endswith(suffix) else s)
    
    @staticmethod
    def find(container: Union[List[TYPE], str], value: TYPE):
        """Returns the index of value in container or -1 if value is not found."""
        if isinstance(container, list):
            try:
                return container.index(value)
            except ValueError:
                return -1
        elif isinstance(container, str):
            return container.find(value)
    @staticmethod
    def pairwise(iterable):
        """Return successive overlapping pairs taken from the input iterable."""
        a, b = tee(iterable)
        next(b, None)
        return zip(a, b)

# ————————————————————— Division line ——————————————————————

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        n = len(nums)
        cnt = 0  # 计数器在外部定义

        @lru_cache(None)
        def dfs(index: int, current_sum: int):
            nonlocal cnt  # 使用 nonlocal 来引用外部的 cnt
            if index == n:
                if current_sum == target:
                    cnt += 1
                return

            # 对当前元素进行加法和减法两种选择，并递归处理下一个元素
            dfs(index + 1, current_sum + nums[index])
            dfs(index + 1, current_sum - nums[index])

        dfs(0, 0)  # 从第一个元素开始，总和初始化为0
        return cnt
    
    def findTargetSumWays(self, nums, target):
        sum_nums = sum(nums)
        # 目标和 target 必须在范围 [-sum_nums, sum_nums] 之间
        if target > sum_nums or target < -sum_nums:
            return 0
        
        dp = std.array(0, 2 * sum_nums + 1)
        dp[sum_nums] = 1  # 初始条件：sum 为 0 的方案数为 1
        
        for num in nums:
            next_dp = std.array(0, 2 * sum_nums + 1)
            for sum_ in range(num, 2 * sum_nums - num + 1):
                next_dp[sum_ + num] += dp[sum_]
                next_dp[sum_ - num] += dp[sum_]
            dp = next_dp
        
        return dp[sum_nums + target]
    
    
    def findTargetSumWays(self, nums, target):
        total_sum = sum(nums)
        if (total_sum - target) % 2 != 0 or total_sum < target:
            return 0
        target_sum = (total_sum - target) // 2

        dp = [0] * (target_sum + 1)
        dp[0] = 1
        
        for num in nums:
            for j in range(target_sum, num - 1, -1):
                dp[j] += dp[j - num]
        
        return dp[target_sum]