理解带备忘录的递归动态规划子集求和算法的时间复杂度

# Returns true if there exists a subsequence of `A[0…n]` with the given sum
def subsetSum(A, n, k, lookup):
 
    # return true if the sum becomes 0 (subset found)
    if k == 0:
        return True
 
    # base case: no items left, or sum becomes negative
    if n < 0 or k < 0:
        return False
 
    # construct a unique key from dynamic elements of the input
    key = (n, k)
 
    # if the subproblem is seen for the first time, solve it and
    # store its result in a dictionary
    if key not in lookup:
 
        # Case 1. Include the current item `A[n]` in the subset and recur
        # for the remaining items `n-1` with the decreased total `k-A[n]`
        include = subsetSum(A, n - 1, k - A[n], lookup)
 
        # Case 2. Exclude the current item `A[n]` from the subset and recur for
        # the remaining items `n-1`
        exclude = subsetSum(A, n - 1, k, lookup)
 
        # assign true if we get subset by including or excluding the current item
        lookup[key] = include or exclude
 
    # return solution to the current subproblem
    return lookup[key]
 
 
if __name__ == '__main__':
 
    # Input: a set of items and a sum
    A = [7, 3, 2, 5, 8]
    k = 14
 
    # create a dictionary to store solutions of subproblems
    lookup = {}
 
    if subsetSum(A, len(A) - 1, k, lookup):
        print('Subsequence with the given sum exists')
    else:
        print('Subsequence with the given sum does not exist')

复杂度推导逻辑 #

• 记忆化搜索的时间复杂度遵循核心规则：每个不重复的子问题只会被计算1次，后续遇到相同子问题直接读取备忘录存储的结果，无需重复计算，因此总时间开销 = 子问题总数量 × 单个子问题的计算开销。
• 子问题总数量计算：
  代码中用二元组(n, k)作为子问题的唯一标识：
  • 第一维n是当前处理到的数组下标，取值范围为0 ~ 数组总长度-1，最多有n种不同取值（n为输入数组的总长度）
  • 第二维k是当前需要凑出的剩余目标和，因为子集和问题默认输入元素均为正整数，剩余和不可能超过原始目标和sum，取值范围为0 ~ sum，最多有sum+1种不同取值
    两个维度组合后，总共有O(n*sum)个不重复的子问题。
• 单个子问题的计算开销：每个子问题首次计算时，除了调用更小的子问题外，仅包含边界判断、键生成、查表、结果存储等O(1)操作，没有额外的循环开销。

最终可得该算法的总时间复杂度为O(n*sum)。 #

补充说明 #

该复杂度属于伪多项式时间复杂度：复杂度和输入的数值sum的大小直接相关，如果sum的量级远大于n（比如sum达到1e9），该算法依然无法高效运行，这也是子集和属于NP难问题的原因，目前不存在真正意义上的多项式时间解法。

内容的提问来源于stack exchange，提问作者wintersun