494. 目标和

admin2024-07-07  3

Powered by:NEFU AB-IN

Link

文章目录

  • 494. 目标和
    • 题意
    • 思路
    • 代码

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. d p [ i ] [ j ] = d p [ i − 1 ] [ j − n u m s [ i ] ] + d p [ i − 1 ] [ j + n u m s [ i ] ] dp[i][j]=dp[i−1][j−nums[i]]+dp[i−1][j+nums[i]] dp[i][j]=dp[i1][jnums[i]]+dp[i1][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: \LeetCode44.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]
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!