leetcode动态规划(十三)-目标和

题目

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

思路

先分析题意可知

将数组分成两个数组,分别为left和right

那么可得

left+right = sum.        式1

left-right = target。    式2

式1和式2合并后可得left=(sum+target)/2

target和sum两个都是固定的,那left就也固定了,题目就转换为从nums中求和为left的集合

问题就转化为,用nums装满容量为的背包,有几种方法

这里的x,就是bagSize,也就是我们后面要求的背包容量。

大家看到(target + sum) / 2 应该担心计算的过程中向下取整有没有影响。

这么担心就对了,例如sum是5,target是2 的话其实就是无解的,所以:

if ((target + sum) % 2 == 1) return 0;

无法整除2就直接返回0表示无法满足

同时如果target 的绝对值已经大于sum,那么也是没有方案的。

if abs(target) > sum: return 0

动规五步曲:

1.确定dp数组(dp table)以及下标的含义

dp[j]表示容量为j的背包装满一共有dp[j]种方法

2.确定递推公式

dp[j] += dp[j-nums[i]]

3.dp数组如何初始化

dp[0] = 1

4.确定遍历顺序

与0-1背包的一维数组一样即可

5.举例推导dp数组

 代码

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        nums_sum = sum(nums)
        if  abs(target) > nums_sum :
            return 0
        if (nums_sum+target)%2 == 1:
            return 0
        target = (nums_sum+target)//2

        dp = [0]*(target+1)
        dp[0] = 1
        for i in range(len(nums)):
            for j in range(target,nums[i]-1,-1):
                dp[j] += dp[j-nums[i]]
        return dp[-1] 

上一篇:Flutter &鸿蒙next中的路由使用详解【基础使用】


下一篇:计算机网络自顶向下(4)---应用层HTTP协议