zählen nein. von Strings

Question

Diese Frage wurde in einer Kodierungsrunde eines Unternehmens in unseren Praktika gestellt.

Gegeben eine Zeichenfolge bestehend aus Zahlen von 1 bis 9. Wir müssen die Zeichenfolge so anordnen, dass sie in Gruppen unterteilt ist. Wir müssen nein zählen. möglicher Strings so, dass die Summe einer Gruppe < = Summe der nächsten fortlaufenden Gruppe ist.

Example1
Eingang 1234
output: 6
Strings sind:

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

die erste Kombination hier 1 4. zweite Kombination, 1 (3 + 4). und so weiter.

Example2
Eingang: 516
Ausgang: 3
Strings sind:

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

Jetzt ist die Zeit, die durch den Weg der brutalen Gewalt benötigt wird, um alle Strings zu erzeugen, O (2^(n-1)). Meine Frage ist, wie man es besser als Brute-Force-Art lösen kann?

Constraint: Eingabestring Länge 1 < = n < = 1000

Answer 1

Dieses Problem effizient gelöst werden können Dynamic Programming verwenden. Ich löste es mit einem zweidimensionalen Array namens dp. Um die Anzahl gültiger Splits zu finden, in der das endte Zeichen zuletzt ist und die letzte Zeichenfolge von start Zeichen beginnt, müssen wir den zuvor berechneten und zwischengespeicherten Wert für die Anzahl gültiger Splits verwenden, der auf das start-1 Zeichen endet. Diese Zahl ist eine Summe aller zwischengespeicherten Werte in dp[prev_start][start - 1], wobei prev_start ein beliebiger Wert zwischen [0, start) sein kann, so dass die Summe der Elemente in s[prev_start:start-1] nicht größer ist als die Summe der Elemente in s[start:end]. Hier ist eine Lösung in Python3:

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

Hinweis: die Zeitkomplexität O (n^4), aber man kann es leicht zu O optimiert (n^3).