algorithm - 如何仅使用加法和减法从整数序列中获取整数

Question

例如，给定一个序列，如 4、10、4、7，我们需要得到 10。答案是 4+10-4=10。建议使用什么样的方法。我可以用DP解决吗？谢谢你!

Answer 1

我想到的最接近动态规划算法的是以下内容(Python):

def find_number(numbers, goal):
    # sum 0 can be reached with empty sequence
    found = {0: []}
    # iterate over all numbers in the list
    for n in numbers:
        # update dict of found numbers with m+n and m-n for each m in found
        found = dict([(m + n, path + [+n]) for (m, path) in found.items()] +
                     [(m - n, path + [-n]) for (m, path) in found.items()])
        # check whether the goal number is among them
        if goal in found:
            return found[goal]

除了递归树遍历算法之外，这可能具有防止某些双重工作的优势，因为中间结果(可以达到序列中某个数字的数字)存储在 HashMap 中。 (也就是说，如果使用前 k 数字的多个组合可以达到某个数字，则只有其中一个存储在 map 中。)可以通过消除中间结果来进一步优化，而中间结果不可能即使加减所有剩余数字的总和也能达到目标。

仍然，就像递归方法一样，最坏情况的复杂度(时间和空间)甚至平均情况的复杂度在列表的长度上仍然是指数级的，因为 found map 在每次迭代中可以加倍。