苏州软软电面

自我介绍+做题
之前没见过的题：给一个串非负整数array和一个target，可以随意加负号然后把所有数字加在一起得到这个target。求的是有多少种方式可以得到这个target。
. From 1point 3acres bbs
大概是用dfs+memoization来做

背包问题吧，

yanjinbin 发表于 2020-12-9 03:05
背包问题吧，

我是用背包来做的 写完了跟面试官沟通得到说expectation是用dfs来做。。当然背包也是可以的

array所有数加起来是S, 然后加上负号的部分和是X
那么S - 2X = target
X = (S - target) / 2
这样就变成了一个背包问题，找到数组里任意个数，使它们的和为X

494（字数字数字数字数）

Linco1n3 发表于 2020-12-08 15:12:54
我是用背包来做的 写完了跟面试官沟通得到说expectation是用dfs来做。。当然背包也是可以的

方便dp下pig什么组么？