c++ - 用于寻找使用字母表进行简单、多重加密的可能方法的算法

Question

当使用一种简单的加密方法时，其中的字母被字母表的索引号代替，有多种解密方法，例如。 ABOR 是 121518，但 121518 也可以是 AYEAH 或 LAER。

好吧，我需要一个算法来计算给定数字有多少种可能的方式来通过描述的方法解密消息(例如 1225 有 5 - ABBE、AVE、ABY、LBE、LY)。

如果你愿意，请帮助我。

Answer 1

你可以递归地做。

前n个数字的编码方式总数是(如果最后一个数字是1 <= d <= 9，则前n-1个数字的编码方式数)+(编码方式的数量如果最后两位数字是 10 <= dd <=26，则为前 n-2 位数字。

缓存结果或使用动态规划来防止指数爆炸。该技术与计算斐波那契数非常相似。

以下是您可以在 Python 中执行此操作的方法，以演示原理:

# s is of form [1-9][0-9]*
s = '121518'
a=1 # Cache of f(i - 2)
b=1 # Cache of f(i - 1)
for i in range(1, len(s)):
   a, b = b, a * (10 <= int(s[i - 1: i + 1]) <= 26) + b * (s[i] != '0')
print b

您可以在 C++ 中以类似的方式完成，但由于这似乎是一项家庭作业/学习练习，我希望您不介意我会让您在 C++ 中解决细节问题。