Converting recursive solution to dynamic programming

Question

Problem statement: find the number of "vowel only" strings that can be made from a given sequence of Morse code (the entire string must be used)

I have this current recursive solution. I want to speed up this algorithm to run in O(n) time. I know that I can define my array as S[j] = the maximum number of unique strings that can be created with access from 1 ... j. But I don't know where to go from there.

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

For future researchers here is the solution for conversion to a DP problem:

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)