Lassen Sie uns sagen, ich habe eine n^n Matrix. In jeder Zelle gibt es eine positive Zahl, und ich muss den Pfad mit dem niedrigsten Gewicht abrufen.den Pfad mit dem niedrigsten Gewicht von Matrix rekursiv abrufen
Weg ist jeder Weg, der in matrix[matrix.length-1][matrix[0].length-1]
in matrix[0][0]
beginnen und enden, ohne Diagonalen.
Gewicht eines Pfads ist die Menge aller Zahlen in seinen Zellen.
Zum Beispiel lassen Sie uns sagen, ich habe diese Matrix:
mat = {{1,2},{3,4}};
so {1,2,4}
ist ein Weg und {1,3,4}
ist ein weiterer Weg.
Das Gewicht des ersten Pfades ist (1 + 2 + 4) und die zweite ein Gewicht von (1 + 3 + 4) hat, so wird die Funktion zurückzukehren.
Ich muss es rekursiv lösen. Der Pseudo-Code sollte wie folgt sein:
if i > matrix.length-1 || i < 0 || j > matrix[0].length-1 || j < 0
//then I passed the borders, so I need to step back.
if i == matrix.length-1 && j == matrix[0].length-1
//Then I reached the last cell, and I need to retrieve sum
Dann vier recursives Anrufe nennen:
public static int smallPath(a, i+1, j, sum);
public static int smallPath(a, i, j+1, sum);
public static int smallPath(a, i-1, j, sum);
public static int smallPath(a, i, j-1, sum);
Dann muss ich etwas holen, was?
Ich weiß, es ist nicht aktuell, aber das ist die allgemeine Idee, kann mir jemand helfen, dies zu lösen? Vielen Dank!
Danke für die Antwort! Welche Parameter muss ich an die Funktion senden? eine für die zufälligen, die sich nicht ändern, und eine für die linken Summen, die immer um die Matrix [x] [y] zunehmen? Ich brauche wirklich etwas Hilfe mit dem Code .. – Avishay28
Oben bearbeitet. Es ist nicht schwer, meine Direktanfluglösung zu finden, aber es ist normalerweise nicht korrekt. –