Betrachten Sie dieses einfachere Problem:
Wenn Sie einen Vektor der Größe N angeben, der nur die Werte 1 und 0 enthält, suchen Sie eine Untersequenz, die genau k Werte von 1 enthält.
Sei A der gegebene Vektor und S[i] = A[1] + A[2] + A[3] + ... + A[i] , was bedeutet, wie viele 1s es in der Untersequenz A[1..i] gibt.
Für jedes i interessiert uns die Existenz von j <= i , also S[i] - S[j-1] == k .
Wir können dies in O(n) mit einer Hash-Tabelle finden, indem wir die folgende Beziehung verwenden:
S[i] - S[j-1] == k => S[j-1] = S[i] - k
Nun können wir dies verwenden, um Ihr gegebenes Problem in O(N^3) zu lösen: Für jede Sequenz von Zeilen in Ihrer gegebenen Matrix (es gibt O(N^2) Reihenfolgen), betrachten Sie diese Sequenz, um einen Vektor darzustellen und den vorherigen Algorithmus anzuwenden darauf. Die Berechnung von S ist im Matrixfall etwas schwieriger, aber es ist nicht so schwer herauszufinden. Lassen Sie mich wissen, wenn Sie weitere Informationen benötigen.
Aktualisierung:
So funktioniert der Algorithmus in der folgenden Matrix: k = 12 :
Betrachten Sie die erste Zeile allein:
%Vor% Betrachte es als Vektor 0 1 1 1 1 0 und wende den Algorithmus für das einfachere Problem an: wir finden, dass es keine Subsequenz gibt, die bis zu 12 addiert, also gehen wir weiter.
Betrachten Sie die ersten beiden Zeilen:
%Vor% Betrachte sie als den Vektor 0+0 1+1 1+1 1+1 1+1 0+0 = 0 2 2 2 2 0 und wende den Algorithmus für das einfachere Problem an: wieder keine Untersequenz, die zu 12 addiert, also mach weiter.
Betrachten Sie die ersten drei Zeilen:
%Vor% Betrachten Sie sie als Vektor 0 3 3 3 3 0 und wenden Sie den Algorithmus für das einfachere Problem an: Wir finden die Sequenz, die an Position 2 beginnt und an Position 5 endet, als Lösung. Von diesem können wir das gesamte Rechteck mit einfacher Buchhaltung erhalten.
Ich kann es mit O machen (N ^ 3 * log (N)), aber sicher ist die beste Lösung schneller. Zuerst erstellen Sie eine weitere N * N-Matrix B (die Anfangsmatrix ist A). Die Logik von B ist die folgende:
%Vor%Sie können B für O (N ^ 2) durch dynamische Programmierung auswerten: B [i] [j] = B [i-1] [j] + B [i] [j-1] - B [i- 1] [j-1] + A [i] [j].
Nun ist es sehr einfach, dieses Problem mit O (N ^ 4) zu lösen, indem man über den gesamten rechten unteren Teil (i = 1..N, j = 1..N, O (N ^ 2)) nach links iteriert -bottom (z = 1..j, O (N)), und rechts-oben (t = 1..i, O (N)) und Sie erhalten die Anzahl der Einsen in diesem Rechteck mit Hilfe von B:
%Vor%Wenn du genau k: k == sum_of_ones hast, dann raus aus dem Ergebnis.
Um es N ^ 3 * log (N) zu machen, sollten Sie rechts-oben durch binäre Suche finden (also nicht nur alle möglichen Zellen iterieren).