Das Problem besteht darin, die minimale Anzahl von Quadraten zu finden, die benötigt werden, um zu einer Zahl n zu addieren.
Einige Beispiele:
%Vor%Ich kenne Lagranges Vier-Quadrate-Theorem , das besagt, dass jede natürliche Zahl dargestellt werden kann als die Summe von vier Quadraten.
Ich versuche das mit DP zu lösen.
Das ist, was ich herausgefunden habe (es ist nicht korrekt)
%Vor%Was ist der richtige DP-Weg, um das zu lösen?
Ich bin mir nicht sicher, ob DP der effizienteste Weg ist, um dieses Problem zu lösen, aber Sie haben nach DP gefragt.
min [i] = min (min [i - 1] + 1, 1 + min [i - prev]) wobei prev eine Quadratzahl & lt; ich
Das ist nahe, ich würde die Bedingung als
Beachten Sie, dass Sie für jedes i verschiedene mögliche Werte von prev prüfen müssen.
Hier ist eine einfache Implementierung in Java.
%Vor%Scheint mir, dass Sie in der Nähe sind ...
Sie nehmen die min () von zwei Begriffen, von denen jeder min[i - p] + 1 ist, wobei p entweder 1 oder irgendein anderes Quadrat & lt; ich.
Um das zu beheben, nehmen Sie einfach min () von min[i - p] + 1 über all p (wobei p ein Quadrat & lt; i ist).
Das wäre ein korrekter Weg. Es kann einen schnelleren Weg geben.
Es kann auch die Lesbarkeit verbessern, wenn Sie min[] und min() verschiedene Namen angeben. : -)
P.S. Der obige Ansatz erfordert, dass Sie min[] entweder explizit oder als Teil Ihres DP-Frameworks memozieren. Andernfalls wäre die Komplexität des Algorithmus aufgrund der Rekursion etwas wie O (sqrt (n)!): - p, obwohl der durchschnittliche Fall viel besser sein könnte.
P. P. S. Siehe @ Nikitas Antwort für eine nette Implementierung. Zu denen würde ich die folgenden Optimierungen hinzufügen ... (Ich bin nicht pingelig seine Implementierung - er präsentierte es als eine einfache.)
j*j*2 <= i oder sogar j*j*4 <= i . Ich denke schon, aber ich habe meinen Kopf nicht komplett um mich herum verstanden. Für großes i wäre es schneller, ein Limit für j vor der inneren Schleife zu berechnen und j direkt mit ihm für die Schleifenbeendigungsbedingung zu vergleichen, anstatt j bei jeder inneren Schleifeniteration zu quadrieren. ZB
%Vor%Auf der anderen Seite brauchen Sie j ^ 2 für den Rekursionsschritt, so lange Sie es speichern, können Sie es genauso gut verwenden.
Für Abwechslung, hier ist eine andere Antwort:
Definiere minsq [i, j] als die minimale Anzahl von Quadraten von {1 ^ 2, 2 ^ 2, ..., j ^ 2}, die sich zu i addieren. Dann ist die Rekursion:
%Vor%d. h., um minsq [i, j] zu berechnen, verwenden wir entweder j ^ 2 oder nicht. Unsere Antwort für n ist dann:
%Vor%Diese Antwort ist vielleicht konzeptionell einfacher als die zuvor präsentierte, aber Code-weise ist es schwieriger, da man mit den Basisfällen vorsichtig sein muss. Die zeitliche Komplexität für beide Antworten ist asymptotisch gleich.
Ich stelle einen verallgemeinerten sehr effizienten dynamischen Programmieralgorithmus vor, um die minimale Anzahl von positiven ganzen Zahlen gegebener Energie zu finden, um ein gegebenes Ziel in JavaScript zu erreichen.
Um zum Beispiel 50000 mit ganzen Zahlen der 4. Potenz zu erreichen, wäre das Ergebnis [10,10,10,10,10] oder 18571 mit ganzen Zahlen der 7. Potenz zu erreichen, würde [3,4] ergeben. Dieser Algorithmus würde sogar mit rationalen Potenzen arbeiten, um 222 mit ganzen Zahlen von zu erreichen, wäre [ 32, 32, 243, 243, 243, 3125 ]
Tags und Links algorithm