如何应用回溯算法？

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（可能的消息数量为308061521170129）。由于我的实现重复次数过多，处理这样的输入需要很长时间。我考虑使用回溯算法，但我还没有意识到如何为连续结果实现记忆化。

如果可能的话，请指出正确的方法来解决这个问题。

- vpetrigo

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

- Paul Hankin

---

似乎对于输入的 12345 有问题。 - Ashot

@Ashot -- 谢谢，你说得对。索引错误了，[i-1:i] 应该是 [i-1:i+1]。现在已经修复了。 - Paul Hankin

@PaulHankin，感谢您的想法，但对于输入11101，它不起作用。您的代码输出为2，而我的正确答案是5。总和是否应以不同的方式累加？ - vpetrigo

啊，我错过了“0”可以单独作为空格的情况。这是一个简单的修复 - 使代码更简单了一些。现在已经修复了。 - Paul Hankin

谢谢你的帮助！ - vpetrigo

Answer 2

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

- David

---

我试图修复get_alpha函数内的for循环，以便顺序获取不超过两个数字，但在这里它不起作用。如果当前取出的数字大于27，则在字典中进行检查会有效地中断。 - vpetrigo

seq[:i] 的意思是“列表中不包括seq[i]的元素”。例如，当程序生成10时，它将生成 seq[1:10]。只需检查 seq[i] 和 seq[i:i+1]。 - David

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - David

@David，正如您所看到的，在每个步骤中都会检查seq中的数字是否在字典中。并且在下一个递归树级别中，他会传递切片序列。 - Ashot

这不是问题。你的代码之所以慢，是因为你在不需要的情况下使用了 seq[:i]。 - David

Answer 3

你可能也意识到308061521170129是第71个斐波那契数。这种关系对应于斐波那契数给出了“某些枚举问题的解决方案。最常见的问题是计算总和为n的1和2的组合数：有Fn+1种方法可以做到这一点”（https://en.wikipedia.org/wiki/Fibonacci_number#Use_in_mathematics）。

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

- גלעד ברקן