DPDPDDP - Memoization (T->B)

[bitmori]

Make it work!

1. 先画出tree来找出暴力递归思路
2. 用递归实现tree
3. 测试

DP问题应该都能画出递归树，把问题简化成子问题+从父问题到子问题的一个步骤

Make it fast!

1. 添加memo词典
2. 添加新的base case来返回从memo中找到的结果
3. 把新生成的值保存到memo里

[bitmori]

例子1: canSum(target, numbers) 能否用numbers中的值相加得到target

暴力解:

def canSum(target, numbers):
    if target == 0:
        return True
    if target < 0:
        return False
    for i in numbers:
        if canSum(target - i, numbers):
            return True
    return False

Memo解:

def canSumMemo(target, numbers, memo):
    if target in memo:
        return memo[target]
    if target == 0:
        return True
    if target < 0:
        return False
    for i in numbers:
        if canSumMemo(target - i, numbers, memo):
            memo[target] = True
            return True
    memo[target] = False
    return False

[bitmori]

例子2: howSum(target, numbers) 如果numbers中的值相加能够得到target，返回这些值组成的数组，否则返回null

暴力解：

def howSum(target, numbers):
    if target == 0:
        return []
    if target < 0:
        return None
    for i in numbers:
        res = howSum(target - i, numbers)
        if res is not None:
            res.append(i)
            return res
    return None

Memo解：

def howSumMemo(target, numbers, memo):
    if target in memo:
        return memo[target]
    if target == 0:
        return []
    if target < 0:
        return None
    for i in numbers:
        res = howSumMemo(target - i, numbers, memo)
        if res is not None:
            res.append(i)
            memo[target] = res
            return memo[target]
    memo[target] = None
    return None

[bitmori]

例子3: bestSum(target, numbers) 如果numbers中的值相加能够得到target，返回这些值组成的数组中元素最少的一个，否则返回null

暴力解：

def bestSum(target, numbers):
    if target == 0:
        return []
    if target < 0:
        return None
    shortestList = None
    for i in numbers:
        res = bestSum(target - i, numbers)
        if res is not None:
            newList = [*res, i]
            if shortestList is None or len(shortestList) > len(newList):
                shortestList = newList
    return shortestList

Memo解：

def bestSumMemo(target, numbers, memo):
    if target in memo:
        return memo[target]
    if target == 0:
        return []
    if target < 0:
        return None
    shortestList = None
    for i in numbers:
        res = bestSumMemo(target - i, numbers, memo)
        if res is not None:
            newList = [*res, i]
            if shortestList is None or len(shortestList) > len(newList):
                shortestList = newList
    memo[target] = shortestList
    return shortestList

[bitmori]

上面的3个例子分别代表了DP的3中类型：

1. canSum -> Decision Problem 定性问题
2. howSum -> Combination Problem 组合定量问题
3. bestSum -> Optimization Problem 优化定量问题

[bitmori]

例子4: canConstruct(target, words) 能否用words中的字符串组合成target字符串

暴力解：

def canConstruct(target, words):
    if not target:
        return True
    for word in words:
        if target.startswith(word):
            suffix = target[len(word):]
            if canConstruct(suffix, words):
                return True
    return False

Memo解：

def canConstructMemo(target, words, memo):
    if target in memo:
        return memo[target]
    if not target:
        return True
    for word in words:
        if target.startswith(word):
            suffix = target[len(word):]
            if canConstructMemo(suffix, words, memo):
                memo[target] = True
                return True
    memo[target] = False
    return False

[bitmori]

例子5: countConstruct(target, words) 找出words中能够组成target的组合数量

暴力解：

def countConstruct(target, words):
    if not target:
        return 1
    count = 0
    for word in words:
        if target.startswith(word):
            suffix = target[len(word):]
            count += countConstruct(suffix, words)
    return count

Memo解：

def countConstructMemo(target, words, memo):
    if target in memo:
        return memo[target]
    if not target:
        return 1
    count = 0
    for word in words:
        if target.startswith(word):
            suffix = target[len(word):]
            count += countConstructMemo(suffix, words, memo)
    memo[target] = count
    return count

[bitmori]

例子6: allConstruct(target, words) 找出所有能组成target的组合

暴力解：

def allConstruct(target, words):
    if not target:
        return [[]]
    result = []
    for word in words:
        if target.startswith(word):
            suffix = target[len(word):]
            suffixCombination = allConstruct(suffix, words)
            targetWays = []
            for it in suffixCombination:
                res = [word, *it]
                targetWays.append(res)
            result.extend(targetWays)
    return result

Memo解：

def allConstructMemo(target, words, memo):
    if target in memo:
        return memo[target]
    if not target:
        return [[]]
    result = []
    for word in words:
        if target.startswith(word):
            suffix = target[len(word):]
            suffixCombination = allConstructMemo(suffix, words, memo)
            targetWays = []
            for it in suffixCombination:
                res = [word, *it]
                targetWays.append(res)
            result.extend(targetWays)
    memo[target] = result
    return result