将递归解决方案转换为动态规划

Question

问题陈述：找出给定的摩尔斯电码序列（必须使用整个字符串）可以组成的"vowel only"个字符串

我有这个当前的递归解决方案。我想在 O(n) 时间内将此算法加速到运行。我知道我可以将我的数组定义为 S[j] = 可以从 1 ... j 访问创建的唯一字符串的最大数量。但我不知道从那里去哪里。

morsedict = {'A': '.-',
             'E': '.',
             'I': '..',
             'O': '---',
             'U': '..-'}

 maxcombinations = 0

 def countCombinations(codelist):
    if len(codelist) is 0:
        global maxcombinations
        maxcombinations += 1
        return

    if codelist[0] in morsedict.values():
        countCombinations(codelist[1:])
    if len(codelist) >= 2 and codelist[:2] in morsedict.values():
        countCombinations(codelist[2:])
    if len(codelist) >= 3 and codelist[:3] in morsedict.values():
        countCombinations(codelist[3:])
    return

Answer 1

对于未来的研究人员，这里是转换为 DP 问题的解决方案：

morsedict = {'A': '.-',
             'E': '.',
             'I': '..',
             'O': '---',
             'U': '..-'}


def countcombinations(codelist):
    # Generate the DP array to match the size of the codeword
    maxcombinations = [0] * (len(codelist))

    # How many unique strings can I create with access to j elements: j = current index
    # j = 0: access to nothing (1 because we need somewhere to start)
    maxcombinations[0] = 1

    # Brute force calculate the first case due to its simplicity
    if codelist[0: 2] in morsedict.values():
        maxcombinations[1] = 1
    else:
        maxcombinations[1] = 0

    # For the rest of the indices, we look back in the DP array to see how good we can do given a certain length string
    for i in range(1, len(codelist)):
        firststr = codelist[i]
        secondstr = codelist[(i - 1): i + 1]
        thirdstr = codelist[(i - 2): i + 1]

        if len(firststr) is 1 and firststr in morsedict.values():
            maxcombinations[i] += maxcombinations[i - 1]
        if len(secondstr) is 2 and secondstr in morsedict.values():
            maxcombinations[i] += maxcombinations[i - 2]
        if len(thirdstr) is 3 and thirdstr in morsedict.values():
            maxcombinations[i] += maxcombinations[i - 3]

    print(maxcombinations[-1])


if __name__ == "__main__":
    input()
    codelist = input()
    countcombinations(codelist)

将递归解决方案转换为动态规划

Converting recursive solution to dynamic programming

dynamic-programming

time-complexity

computation-theory