力扣每日一题 6/30 记忆化搜索/动态规划

• 博客主页：誓则盟约
• 系列专栏：IT竞赛 专栏
• 关注博主，后期持续更新系列文章
• 如果有错误感谢请大家批评指出，及时修改
• 感谢大家点赞👍收藏⭐评论✍ 

---

494.目标和【中等】

题目：

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

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

• 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 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

示例 2：

输入：nums = [1], target = 1
输出：1

提示：

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 1000
• 0 <= sum(nums[i]) <= 1000
• -1000 <= target <= 1000

---

分析问题：

设 nums 的元素和为 s，添加正号的元素之和为 p，添加负号的元素（绝对值）之和为 q，那么有

• p+q=s
• p-q=target

化简得：

• p = (s+target) / 2 
• q = (s-target) / 2

        我们找所有元素里面选取出来的元素和恰好为p的方案个数，那么这就变成了一道经典的0-1背包问题的变形，找恰好装capacity,求方案数/最大/最小价值和，capacity指的是容量，也就是这里的负数的和的绝对值。

        那么我们就可以根据传统的0-1背包问题的求解过程来解题，带上cache数组以便达到记忆化的一个效果。

        此处也可以进行进一步的优化，用一个二维数组f来替代递推函数dfs：

        首先创建一个二维数组f，其中n表示数组的长度，target表示目标值，该数组用于记录不同状态下的结果。

        然后将f[0][0]初始化为1，这是一个基础的起始条件。接下来通过两个嵌套循环进行计算。外层循环遍历一个名为nums的数组，其中的每个元素x代表物品的价值。内层循环遍历目标值target的所有可能取值。在循环内部，根据不同条件更新f数组的值。

•         如果c小于x，说明当前考虑的物品价值x大于当前的目标值c，无法选择该物品，所以f[i + 1][c]保持与f[i][c]相同。
•         如果c大于或等于x，那么f[i + 1][c]等于f[i][c]加上f[i][c - x]，这表示在这种情况下，可以选择该物品，所以要将不选择该物品的情况（f[i][c]）和选择该物品的情况（f[i][c - x]）的结果相加。

        最后，函数返回f[n][target]，即最终在考虑了所有物品和目标值的情况下的结果。

代码实现：

优化前：

class Solution:
    def findTargetSumWays(self, nums: list[int], target: int) -> int:
        # p = (s+t) /2
        target += sum(nums)
        if target < 0 or target % 2:
            return 0
        target //=2
        n=len(nums)
        @cache  # 保存记忆
        def dfs(i,c): # 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)

 

优化后:

class Solution:
    def findTargetSumWays(self, nums: list[int], target: int) -> int:
        # p = (s+t) /2
        target += sum(nums)
        if target < 0 or target % 2:
            return 0
        target //=2
        n=len(nums)
 
        f=[[0]*(target+1) for _ in range(n+1)]
        f[0][0]=1
        for i,x in enumerate(nums):
            for c in range(target+1):
                if c1][c] = f[i][c]
                else: f[i+1][c] = f[i][c] + f[i][c-x]
        return f[n][target]

---

 

总结：

优化后代码详细解释：

1. target += sum(nums)：将target值加上数组nums的元素总和，得到p的2倍。
2. if target < 0 or target % 2:：检查新的target值是否小于0或是否为奇数。如果是，则直接返回0，表示无法得到目标值。
3. target //= 2：将target值除以2，得到用于后续计算的新值。
4. n = len(nums)：获取数组nums的长度。
5. f = [[0] * (target + 1) for _ in range(n + 1)]：创建一个二维数组f，用于动态规划的计算。
6. f[0][0] = 1：设置初始状态，即当没有元素且目标值为0时，有一种方法可以达到。
7. 通过两个嵌套循环进行动态规划计算：
   • 外层循环for i, x in enumerate(nums):遍历数组nums的每个元素。
   • 内层循环for c in range(target + 1):遍历所有可能的目标值。
   • 在循环内部，根据当前元素x和目标值c的关系更新f[i + 1][c]的值。如果c < x，则f[i + 1][c] = f[i][c]，表示无法选择当前元素来达到目标值；如果c >= x，则f[i + 1][c] = f[i][c] + f[i][c - x]，表示可以选择或不选择当前元素来达到目标值，将两种情况的方法数相加。
8. 最后，函数返回f[n][target]，即使用整个数组nums达到最终目标值的方法数。

---

考点：

1. 动态规划的应用：通过构建二维数组来记录不同状态下的结果，根据状态转移方程进行计算。
2. 对问题的数学转化：将原问题转化为通过加减运算得到特定值的问题，并进行了一些预处理和条件判断。

收获：

1. 深入理解了动态规划的思想和应用方法，学会如何根据问题的特点构建合适的状态和状态转移方程。
2. 提高了对问题进行数学分析和转化的能力，能够将复杂的问题简化为可计算的形式。
3. 增强了对数组操作和循环的熟练程度，能够灵活运用这些基本编程技巧来解决实际问题。

 “对于我们的幸福来说，别人的看法在本质上来讲并不十分重要。”——《人生的智慧》