我遇到了一个棘手的问题.给定: A = [a1,a2,... an](长度为"n"的正整数列表) r(正整数)
找到{*,+}运算符列表O = [o1,o2,... on-1],这样如果我们将这些运算符放在"A"元素之间,则生成的表达式将计算为"r".只需要一种解决方案.
因此,例如,如果A = [1,2,3,4] r = 14则O = [*,+,*]
我已经实现了一个简单的递归解决方案和一些优化,但当然它是指数O(2 ^ n)时间,因此对于长度为40的输入,它可以工作多年.
我想问你们有没有人知道这个指数的解决方案吗？
A的更新元素在0-10000之间,r可以任意大