How to apply a backtracking algorithm?
<p>I'm doing some excercises in Python course and one of them where I'm stuck is below:</p>

<pre><code>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)
</code></pre>

<p>The naive solution is easy and it is simple bruteforce algorithm:</p>

<pre><code>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()
</code></pre>

<p>But as the length of an input sequence might be as long as 100 characters and there might be lots of repetition I have met a time limits. For example, one of the sample input is <code>2222222222222222222222222222222222222222222222222222222222222222222222 (possible messages number is 308061521170129)</code>. As my implementation makes too many repetition it takes ages for processing such an input. I think of using the backtracking algorithm, but I haven't realised yet how to implement the memoization for the succesive results.</p>

<p>I'd be glad if it is possible to point me out to the right way how to break that task.</p>

<p>You may have also recognized 308061521170129 as the 71st Fibonacci number. This relationship corresponds with the Fibonacci numbers giving "the solution to certain enumerative problems. The most common such problem is that of counting the number of compositions of 1s and 2s that sum to a given total n: there are Fn+1 ways to do this" (<a href="https://en.wikipedia.org/wiki/Fibonacci_number#Use_in_mathematics" rel="nofollow">https://en.wikipedia.org/wiki/Fibonacci_number#Use_in_mathematics</a>).</p>

<p>Every contiguous subsequence in the string that can be divided into either single or double digit codes represents such an <code>n</code> with multiple possible compositions of 1s and 2s; and thus, for every such subsequence within the string, the result must be multiplied by the (subsequence's length + 1) Fibonacci number (in the case of the 70 2's, we just multiply 1 by the 71st Fibonacci number).</p>

python algorithm backtracking