バックトラッキングアルゴリズムの適用方法は？

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文字までになる可能性があり、時間制限を満たしていることが多かったかもしれません。たとえば、サンプル入力の1つは2222222222222222222222222222222222222222222222222222222222222222222222 (possible messages number is 308061521170129)です。私の実装はあまりにも多くの繰り返しを行うので、そのような入力を処理するには時間がかかります。私はバックトラッキングアルゴリズムを使うことを考えていますが、私はまだ成功した結果のためにメモを実装する方法をまだ認識していません。

私は、正しい方法でそのタスクを中断する方法を教えてもらえれば嬉しいです。

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

また、第71番目のフィボナッチ数として308061521170129が認識されていることがあります。この関係はフィボナッチ数が「ある列挙問題の解を与える」ことに対応しています。最も一般的な問題は、与えられた合計nに合計1と2の構成の数を数えることです：Fn + 1の方法があります"（https://en.wikipedia.org/wiki/Fibonacci_number#Use_in_mathematics）。

文字列内の1桁または2桁の数字コードに分割できるすべての連続したサブシーケンスは、1と2の複数の可能な構成を持つようなnを表します。したがって、文字列内のすべてのそのようなサブシーケンスに対して、結果は（サブシーケンスの長さ+ 1）フィボナッチ数（70 2の場合は、1を第71番目のフィボナッチ数で乗算する）で乗算する必要があります。