Ich denke über dieses Topcodierer-Problem nach.
Geben Sie bei einer gegebenen Ziffernfolge die Mindestanzahl an Hinzufügungen an, die erforderlich sind, damit die Zeichenfolge einer Zielnummer entspricht. Jeder Zusatz entspricht dem Einfügen eines Pluszeichens irgendwo in die Ziffernfolge. Nachdem alle Pluszeichen eingefügt wurden, bewerten Sie die Summe wie üblich.
Betrachten Sie zum Beispiel "303" und eine Zielsumme von 6. Die beste Strategie ist "3 + 03".
Ich würde es mit roher Gewalt wie folgt lösen:
%Vor%Macht es Sinn? Ist es vom Standpunkt der Leistung optimal?
...
Nun, jetzt sehe ich, dass eine dynamische Programmierlösung effizienter sein wird. Es ist jedoch interessant, ob die vorgestellte Lösung überhaupt Sinn macht.
Es ist sicherlich nicht optimal. Wenn Sie beispielsweise die Zeichenfolge "1234567890" erhalten und das Ziel eine dreistellige Zahl ist, wissen Sie, dass Sie die Zeichenfolge in mindestens vier Teile aufteilen müssen, sodass Sie keine 0, 1 oder 2 Einfügungen überprüfen müssen . Außerdem begrenzt das Ziel den Bereich zulässiger Einfügepositionen. Beide Punkte haben geringe Auswirkungen auf kurze Saiten, können aber bei längeren Saiten einen großen Unterschied machen. Allerdings vermute ich, es gibt eine weitaus bessere Methode, riecht ein bisschen DP.
Da die Eingabegröße klein ist (10), sind alle möglichen Wege (die durch einen einfachen Binärzähler der Länge 10 gefunden werden können) klein (2 ^ 10 = 1024), so dass Ihr Algorithmus schnell genug ist und ein gültiges Ergebnis zurückgibt IMO gibt es keine Notwendigkeit, es zu verbessern.
Alles in allem, bis Ihre Lösung in Zeit und Speicher und anderen gegebenen Einschränkungen gut funktioniert, ist keine Mikrooptimierung erforderlich. Dieser Fall, wie akappa angeboten wird, kann mit DP wie DP im Zwei-Partitionen-Problem gelöst werden, aber wenn Ihr Algorithmus schnell ist, besteht keine Notwendigkeit, dies zu tun und kann eine große Konstante hinzufügen oder Code unlesbar machen.
Ich biete nur parse Stellen der Zeichenfolge einmal (in Array der Länge 10), um zu viele String-Parsing zu verhindern, und verwenden Sie einfach ein * 10 ^ k + ... (Auch Sie können 10 ^ k für k = berechnen 0..9 beim Start und speichern Sie den Wert).
Ich denke, das Problem ist ähnlich dem Matrix Chain Multiplication-Problem, bei dem Klammern für die geringste Multiplikation gesetzt werden müssen. Hier stellen Klammern "+" dar. Also ich denke, es könnte durch ähnliche dp Ansatz gelöst werden. Versuchen Sie es zu implementieren.
Scheint zu spät zu sein .. aber lies einfach einige Kommentare und Antworten hier, die nein zu dp approach sagen. Aber es ist ein sehr einfaches dp, ähnlich wie das Rod-Cutting-Problem:
Um die Essenz zu bekommen:
%Vor%Einfach ausgedrückt, um dp [i] [j] zu berechnen, nehmen Sie die Position k des letzten '+' Symbols an und kehren dann für s [0..k]
zurückTags und Links algorithm combinatorics