本帖最后由 l0stparadise 于 2020-3-24 14:22 编辑
动态规划学习中，感觉好难
def f358(nums,s):
if s>sum(nums) or s<-sum(nums):
return 0
if (sum(nums)+s)%2:
return 0
else:
real_s=int((sum(nums)+s)/2)
dp_list=[*(real_s+1) for _ in range(len(nums)) ]
for _ in range(0,real_s+1):
if nums==_:
dp_list=1
for _ in range(0,len(nums)):
dp_list=1
for i in range(1,len(nums)):
for k in range(1,real_s+1):
if nums<=k:
dp_list=dp_list+dp_list]
else:
dp_list = dp_list
return dp_list[-1][-1]
def solve(nums:list,num:int):
num = sum(nums)-num
if num%2 != 0:
return 0
target = int(num/2)
def combinationSum2(candidates, target):
def dfs(nums, target, start, visited, path, res):
if target == 0:
res.append(path + [])
return
for i in range(start, len(nums)):
if target - nums < 0:
return 0
if i not in visited:
visited.add(i)
path.append(nums)
dfs(nums, target - nums, i + 1, visited, path, res)
path.pop()
visited.discard(i)
candidates.sort()
res = []
visited = set([])
dfs(candidates, target, 0, visited, [], res)
return res
return len(combinationSum2(nums, target))
print(solve(, 3))
本帖最后由 776667 于 2020-3-24 17:31 编辑
from itertools import permutations
def fun358(nums,s):
result,n = 0,[]
symbols = ['+' for i in range(len(nums))] + ['-' for i in range(len(nums))]
for i in permutations(symbols,len(nums)):
n.append(i)
n = list(set(n))
for i in n:
formula = ''.join(+str(nums) for j in range(len(nums))])
if eval(formula) == s:
result += 1
return result
kinkon 发表于 2020-3-23 19:01
貌似要用到动态规则或者递归
108 ms
塔利班 发表于 2020-3-23 19:45
暴力
动态规划的解答错误
输入：nums = , s = 1
输出：1
预期结果：2
第一个超时
March2615 发表于 2020-3-23 20:09
80 ms
永恒的蓝色梦想 发表于 2020-3-23 20:37
悬赏50，nb
好久没发悬赏题了……
一个账号 发表于 2020-3-23 20:18
628 ms
zltzlt 发表于 2020-3-24 17:55
动态规划的解答错误
输入：
已改
塔利班 发表于 2020-3-23 19:45
暴力
大佬麻烦解释一下第二段代码是啥意思
def func358(nums,s):
if sum(nums)<abs(s) or (s + sum(nums)) % 2 != 0:
return 0
def dg(a,b):
if len(a)==1:
return int(0 in (a+b,b-a))
else:
return dg(a,b+a)+dg(a,b-a)
return dg(nums,s)
1556134029 发表于 2020-3-24 18:11
大佬麻烦解释一下第二段代码是啥意思
如果是长度1的Nums就检查这个数添加正负号是否=s
如果大于1，就吧第一个数单拿出来，把他和s组合到一起，然后剩下的Nums继续，如此递归直到满足长度1截止
import itertools
import numpy as np
def sum_equal(nums, result):
signs = 0
in_vector = np.array(nums)
sign_permutations = []
length = len(nums)
for i in range(length):
sign_permutations.append(1)
sign_permutations.append(-1)
sign_set = set(list(itertools.combinations(sign_permutations, length)))
for sign_vector in sign_set:
if np.dot(in_vector, np.array(sign_vector)) == result:
signs += 1
return signs
本帖最后由 suchocolate 于 2020-3-24 20:05 编辑
我的思路：
1）全是+号算一下：
2）全是-号算一下：
3）其他情况用排列组合出置-1 index列表，分别算出sum。
from itertools import combinations as cb
def fun358(nums, s):
# 生成一个等长index列表
loc = list(range(len(nums)))
# 初始化计数器变量
count = 0
# 全为正值时
if sum(nums) == s:
count += 1
# 全为负数时
if 0 - sum(nums) == s:
count += 1
# 1到n-1个负数时
for n in range(1, len(nums)):
# 找出可能的组合
cb_ls = list(cb(loc, n))
# 循环这个组合列表，列表的元素是元组
for x in cb_ls:
# 复制一个nums的临时列表，用以根据index设置负数
tmp_nm = nums.copy()
# 循环这个元组，设置临时列表的相应位置的元素为负数
for y in x:
tmp_nm = -1 * tmp_nm
# 计算和，如果和等于s，那么计数器+1
if sum(tmp_nm) == s:
count += 1
return count
def calculate(list_, num, result = 0, tmpList = [], length = 0):
if not length:
length = len(list_)
list_1 = list_.copy()
result1 = result
tmpList_ = tmpList.copy()
tmpList1 = tmpList.copy()
if(len(list_)>0):
result += list_
tmpList_ += ]
if(result == num and len(tmpList_) == length):
print(tmpList_, " = ", num)
list_.pop(0)
calculate(list_, num, result, tmpList_, length)
result1 -= list_1
tmpList1 += [-list_1]
if(result1 == num and len(tmpList1) == length):
print(tmpList1, " = ", num)
list_1.pop(0)
calculate(list_1, num, result1, tmpList1, length)
kinkon 发表于 2020-3-23 19:01
貌似要用到动态规则或者递归
大神太强了{:10_266:}可以麻烦解析一下这个算法吗
TJBEST 发表于 2020-3-23 20:30
两个版本，大同小异，一个是用字典存储中间数据，一个纯递归。希望楼主都测一测，我不知道哪一个更快。
...
输入 nums = , s = 25 超时
风魔孤行者 发表于 2020-3-23 20:55
解答错误
输入：nums = , s = 1
输出：0
预期结果：1
ouyunfu 发表于 2020-3-23 21:02
挑战一行代码
如果是python3.8版本，可以使用海象运算符“:=”,减少一次len函数的调用，代码如下：
第二段代码有错哦
ouyunfu 发表于 2020-3-23 21:02
挑战一行代码
如果是python3.8版本，可以使用海象运算符“:=”,减少一次len函数的调用，代码如下：
第一段代码输入以下数据超时：
nums = , s = 1