算法每日一题(三)

算法每日一题(三) 动态规划：目标和！ 题目描述

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

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

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

来源：力扣（LeetCode）

 

题目地址

示例 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

分析

数组可以分成两个部分一个是我们求的那一部分(用left表示),另一部分(用right表示)是与之相减的那一部分,可以得到left+rgylin=sum, left-right= target相加

=>继而得到 left=(target+right)//2

 利用回溯算法

'''可以将nums分成两部分left 和right
其中 left+right=sum
    left-right=target
    带入得到
    left = (sum+target)//2
    sum和target是固定的
    所以就转化成找一个left 数组使得 求和为(sum+target)//2
    那么就变成了求组合问题
'''

#用回溯
path=[]
result=[]
count=0
def backTo(s, t, startIndex,sum_t):
    global count
#查看是否满足条件
    if(sum_t>t):
        return
    if(sum_t==t):
        count+=1
        return
    for i in range(startIndex,len(s)):
        sum_t+=s[i]
        path.append(s[i])
        backTo(s,t,i+1,sum_t)
        #回溯
        path.pop()
        sum_t -= s[i]


nums =  [1,1,1,1]
target=3
if(sum(nums)+target==1):
    print(0)
t= (sum(nums)+target)//2

t=abs(t)
backTo(nums,t,0,0)
return result

 

 利用动态规划

首先确定dp具体表示的是:dp[j]  容量为j时所 有几种方法来满足target推导dp : 举个例子=>d[5] ，num[i] =2 等于什么 呢  d[5] 可以由 容量为3 也就是dp[3] 再加上容量为2 即:dp[3+2] 求得 所以dp[j]= dp[j-num[i]]初始化:dp[0] 容量为0时 即装满容量0 的背包,即0个物品所以由1种

编写代码

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:

        if(sum(nums) 
这里注意一点就是: 当target为负的时候,要给他绝对值,因为 挑30个负的,就等于时挑三十个负的
 
如果不加的话,会报错 比如
 
 
 最终效果为
 
 
 总结 
j容量的最大种数dp[j] 为 上一个状态即dp[j-num[i]]得来.
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5722041.html