How to apply the reverse tracking algorithm?

Question

I am doing some exercises in a Python course, and one of them where I am stuck is below:

Given a digit sequence that represents a message where each uppercase letter 
is replaced with a number (A - 1, B - 2, ... , Z - 26) and space - 0. 
Find the number of the initial messages, from which that sequence 
could be obtained.

Example: 12345 - 3 (ABCDE, LCDE, AWDE)
         11 - 2 (AA, K)

The naive solution is easy and it is a simple brute force algorithm:

import string

def count_init_messages(sequence):
    def get_alpha(seq):
        nonlocal count

        if len(seq) == 0:
            count += 1
            return

        for i in range(1, len(seq) + 1):
            if seq[:i] not in alph_table:
                break
            else:
                get_alpha(seq[i:])

    alphabet = " " + string.ascii_uppercase
    # generate dictionary of possible digit combination
    alph_table = {str(n): alph for n, alph in zip(range(len(alphabet)), alphabet)}
    # counter for the right combination met
    count = 0
    get_alpha(sequence)

    return count

def main():
    sequence = input().rstrip()
    print(count_init_messages2(sequence))

if __name__ == "__main__":
    main()

But since the length of the input sequence can reach 100 characters, and there can be many repetitions, I met time limits. For example, one of the sample input 2222222222222222222222222222222222222222222222222222222222222222222222 (possible messages number is 308061521170129). Since my implementation does too many repetitions, it takes age to process such input. I am thinking about using a backtracking algorithm, but I have not yet figured out how to implement memoirization for successful results.

I would be glad if you can point me to the right path, how to break this task.

Answer 1

, ( s - , a b - ):

 S("") = 1
 S(a) = 1
 S(s + a + b) = S(s+a) + (S(s) if ab is between 10 and 26)

, . , O (n) O (1).

def seq(s):
    a1, a2 = 1, 1
    for i in xrange(1, len(s)):
        a1, a2 = a1 + (a2 if 9 < int(s[i-1:i+1]) < 27 else 0), a1
    return a1

print seq('2222222222222222222222222222222222222222222222222222222222222222222222')

Answer 2

26, 2. for . , .

Answer 3

, 308061521170129 71- . , " ". 1s 2s, n: Fn + 1 "( https://en.wikipedia.org/wiki/Fibonacci_number#Use_in_mathematics).

Each continuous subsequence in a string, which can be divided into single or double-digit codes, represents nwith several possible compositions of 1s and 2s; and therefore, for each such subsequence within the string, the result should be multiplied by the Fibonacci number (the number of the subsequence + 1) (in the case of 70 2, we simply multiply 1 by the 71st Fibonacci number).