如何应用回溯算法？

Question

我正在 Python 课程中做一些练习，下面是我遇到的问题之一：

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)

天真的解决方案很简单，它是简单的暴力算法：

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()

但是由于输入序列的长度可能长达 100 个字符并且可能有很多重复，所以我遇到了时间限制。例如，样本输入之一是 2222222222222222222222222222222222222222222222222222222222222222222222 (possible messages number is 308061521170129)。由于我的实现重复太多，因此处理此类输入需要很长时间。我想到了回溯算法，但我还没有意识到如何实现对连续结果的记忆。

如果可以为我指出如何完成该任务的正确方法，我会很高兴。

Answer 1

查找中的最大数字 table 是 26，因此您永远不需要查找长度大于 2 的字符串。相应地修改 for 循环。这可能足以使蛮力可行。

Answer 2

你要解的递归关系（其中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) space 复杂度。

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 3

您可能还认出了 308061521170129 是第 71 个斐波那契数。这种关系对应于给出 "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" (https://en.wikipedia.org/wiki/Fibonacci_number#Use_in_mathematics).

的斐波那契数列

字符串中的每一个连续的子序列，可以分为一个或两个数字代码，代表这样一个 n 具有多种可能的 1 和 2 组合；因此，对于字符串中的每个这样的子序列，结果必须乘以（子序列的长度 + 1）斐波那契数（在 70 个 2 的情况下，我们只需将 1 乘以第 71 个斐波那契数）。

如何应用回溯算法？

How to apply a backtracking algorithm?

python

algorithm

backtracking