カウント数。文字列の

Question

この質問は、私たちのプレースメントの会社のコーディングラウンドで尋ねられました。

は、我々は、それがグループに分割されるように文字列を配置する必要があり、1から9までの数字からなる文字列を考えます。私たちは何もないと数える必要があります。グループの合計である可能性のある文字列の数< =次の連続するグループの合計。

例1
入力：1234
出力：6つの
文字列である：

• {1,2,3,4}
• {1,2,34}
• {12 、3,4}
• {12,34}
• {1,234}
• {1234}

ここで第一の組み合わせ、1 前記第2の組合せ、1 （3 + 4）。等々。

例2
入力：516
出力：3
文字列は次のとおり

• {5,16}
• {51,6}
• {516}

すべての文字列を生成するための総当たりの時間は、O（2 ^（n-1））です。 私の質問はどのようにブルートフォースよりも優れた方法でそれを解決することですか？

制約：入力文字列の長さ1 < = N = 1000 <

Answer 1

この問題を効率的Dynamic Programmingを用いて解くことができます。私はdpと呼ばれる2次元配列を使ってそれを解決しました。 end番目の文字が最後で、最後の文字列がstart番目の文字から始まる有効な分割数を見つけるために、我々はstart-1番目の文字で終わる有効な分割数のため、以前に計算され、キャッシュされた値を使用する必要があります。この数値は、dp[prev_start][start - 1]のキャッシュされたすべての値の合計です。prev_startは、の要素の合計がs[start:end]の要素の合計を超えないように、[0, start)の間の任意の値になります。

def get_count(s): 
    N = len(s) 
    # Initialize memoization matrix 
    # First row all ones, all others zeros 
    dp = list() 
    dp.append([1] * N) 
    for i in range(N - 1): 
     dp.append([0] * N) 

    # Convert characters to integers 
    s = [ord(i) - ord('0') for i in s] 

    for start in range(1, N): 
     for end in range(start, N): 
      for prev_start in range(0, start): 
       if sum(s[prev_start:start]) <= sum(s[start:end+1]): 
        dp[start][end] += dp[prev_start][start - 1] 

    return sum([dp[i][N - 1] for i in range(N)]) 

print(get_count('516')) 

注：ここではPython3内の溶液は、時間の複雑さはO（N^4）ですが、簡単にO（nは^ 3）にそれを最適化することができます。