将递归解决方案转换为动态编程

Question

问题陈述：找到可以从给定的莫尔斯码序列中产生的“仅元音”字符串的数量（必须使用整个字符串）

我有这个当前的递归解决方案。我想加快这个算法在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)