494. 目标和

发表于2024-07-01更新于2024-07-11字数统计1.6k阅读时长14分阅读次数

摘要
Title: 494. 目标和
Categories: dp, 背包, dfs

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]]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] 的值就是所求结果。

  4. dp背包问题（简单版）dfs+记忆化搜索
    其实dp递推 = dfs+记忆化搜索，将01背包写成dfs形式，非常直观好理解

    1
    2
    3
    4
    5
    6
    7
    8
    9
    @lru_cache(None)
    def dfs(i, c):
        if i < 0: # 当i < 0 时说明选完了，当 c = 0 时说明恰好用完，那就是一种方案
            return 1 if c == 0 else 0
        if c < nums[i]: # 如果体积不够就不选
            return dfs(i - 1, c)
        return dfs(i - 1, c) + dfs(i - 1, c - nums[i]) # 由 i - 1的两个状态转移而来

    return dfs(n - 1, target_sum)

  5. 拓展：

    • 如果至多target_sum呢？
    1
    2
    3
    4
    5
    6
    7
    8
    9
    @lru_cache(None)
    def dfs(i, c):
        if i < 0: 
            return 1 # 这里就不用判断了，能递归到终点说明 c>=0，所以能走到这一步的都是答案
        if c < nums[i]: 
            return dfs(i - 1, c)
        return dfs(i - 1, c) + dfs(i - 1, c - nums[i]) 

    return dfs(n - 1, target_sum)
    • 如果至少target_sum呢？
    1
    2
    3
    4
    5
    6
    7
    8

    @lru_cache(None)
    def dfs(i, c):
        if i < 0:
            return 1 if c <= 0 else 0 # 这里改成小于等于0，因为c是相对于target_sum的值，而且下面的判断也不需要了，因为那是不让c小于0的判断
        return dfs(i - 1, c) + dfs(i - 1, c - nums[i])

    return dfs(n - 1, target_sum)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
'''
Author: NEFU AB-IN
Date: 2024-06-30 21:25:56
FilePath: \LeetCode\494\494.py
LastEditTime: 2024-07-11 22:25:35
'''
# 3.8.19 import
import random
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, comb, fabs, floor, gcd, log, perm, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin
from typing import Any, Dict, List, Tuple, TypeVar, Union

# Constants
TYPE = TypeVar('TYPE')
N = int(2e5 + 10)  # If using AR, modify accordingly
M = int(20)  # If using AR, modify accordingly
INF = int(2e9)
OFFSET = int(100)
MOD = int(1e9 + 7)

# Set recursion limit
setrecursionlimit(INF)


class Arr:
    array = staticmethod(lambda x=0, size=N: [x() if callable(x) else x for _ in range(size)])
    array2d = staticmethod(lambda x=0, rows=N, cols=M: [Arr.array(x, cols) for _ in range(rows)])
    graph = staticmethod(lambda size=N: [[] for _ in range(size)])

    @staticmethod
    def to_1_indexed(data: Union[List, str, List[List]]):
        """Adds a zero prefix to the data and returns the modified data and its length."""
        if isinstance(data, list):
            if all(isinstance(item, list) for item in data):  # Check if it's a 2D array
                new_data = [[0] * (len(data[0]) + 1)] + [[0] + row for row in data]
                return new_data, len(new_data) - 1, len(new_data[0]) - 1
            else:
                new_data = [0] + data
                return new_data, len(new_data) - 1
        elif isinstance(data, str):
            new_data = '0' + data
            return new_data, len(new_data) - 1
        else:
            raise TypeError("Input must be a list, a 2D list, or a string")


class Math:
    max = staticmethod(lambda a, b: a if a > b else b)
    min = staticmethod(lambda a, b: a if a < b else b)


class IO:
    input = staticmethod(lambda: stdin.readline().rstrip("\r\n"))
    read = staticmethod(lambda: map(int, IO.input().split()))
    read_list = staticmethod(lambda: list(IO.read()))


class Std:
    pass

# ————————————————————— 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 = Arr.array(0, 2 * sum_nums + 1)
        dp[sum_nums] = 1  # 初始条件：sum 为 0 的方案数为 1

        for num in nums:
            next_dp = Arr.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]

    def findTargetSumWays(self, nums, target):
        n = len(nums)
        total_sum = sum(nums)
        if (total_sum - target) % 2 != 0 or total_sum < target:
            return 0
        target_sum = (total_sum - target) // 2

        @lru_cache(None)
        def dfs(i, c):
            if i < 0:
                return 1 if c == 0 else 0
            if c < nums[i]:
                return dfs(i - 1, c)
            return dfs(i - 1, c) + dfs(i - 1, c - nums[i])

        return dfs(n - 1, target_sum)

使用搜索：谷歌必应百度