子数列的记忆迭代法问题的解法

Question

第一个用了迭代法计算成功了

def targetSum(S, i,  tgt):
    # your code here
    k = len(S)
    
    # If calculation with this input is already computed return result from mem

    
    if tgt < 0:
        return float('inf')
    if i >= k and tgt >= 0:
        return tgt
    else:        
        minimum =  min(targetSum(S, i+1, tgt-S[i]), targetSum(S, i+1, tgt))
        
        # Store result of current calculation in mem if needed again later
        print(minimum)
        return minimum
        
def tgtSum(tgt, S):
    return targetSum(S, 0, tgt)

t6 = (tgtSum(457, [11, 23, 37, 48, 94, 152, 230, 312, 339, 413])) # should be 1
assert t6 == 1, 'Test 6 failed'   

第二个问题

def memoTargetSum(S, tgt):
    k = len(S)
    assert tgt >= 0
    ## Fill in base case for T[(i,j)] where i == k
    T = {} # Memo table initialized as empty dictionary
    for j in range(tgt+1):
        T[(k,j)] = j
    # your code here
    
    for i in range(k-1,-1,-1):
        for j in range(tgt,-1,-1):
            if T[(i + 1, j)]-S[i] < 0:
                T[(i,j)] = T[(i + 1, j)]
            else: 
                T[(i,j)] = T[(i + 1, j)]-S[i]
    
    
    return T

第二个代码有的成功，有的没有成功
a2= [1, 2, 3, 4, 5, 10]
成功了
a3= [11, 23, 37, 48, 94, 152, 230, 312, 339, 413]
没有成功，为什么？
还有第三个问题

给出的代码是：

def getBestTargetSum(S, tgt):
    k = len(S)
    assert tgt >= 0
    # your code here
    
    return res

验证代码为：

def checkTgtSumRes(a, tgt,expected):
    a = sorted(a)
    res = getBestTargetSum(a, tgt)
    res = sorted(res)
    print('Your result:' , res)
    assert tgt - sum(res)  == expected, f'Your code returns result that sums up to {sum(res)}, expected was {expected}'
    i = 0
    j = 0
    n = len(a)
    m = len(res)
    while (i < n and j < m):
        if a[i] == res[j]: 
            j = j + 1
        i = i + 1
    assert j == m, 'Your result  {res} is not a subset of {a}'


print('--test 1--')
a1 = [1, 2, 3, 4, 5, 10]
print(a1, 15)
checkTgtSumRes(a1, 15, 0)

print('--test 2--')
a2 = [1, 8, 3, 4, 5, 12]
print(a2, 26)
checkTgtSumRes(a2, 26, 0)

这个该怎么写？

Answer 1

记忆化递归，是有一个变量记录曾经递归过的东西，然后每次递归前先查询，有的话直接返回，没有的话再去计算。你这第二问代码绝对不是记忆化递归，因为没有查询是否存在，而是通通计算。看代码样式推测你写的动态规划，离题甚远了。