Wie Design/Word dynamische Programmierung Subprobleme?

Question

Ich probiere die Bottom-up-Methode zur dynamischen Programmierung aus und habe ein paar Probleme damit.

Ich habe gelernt, die erforderliche Lösung zu erreichen, indem Sie zuvor berechnete Werte entweder in einem 1D- oder 2D-Array speichern und bei Bedarf darauf Bezug nehmen. Das Problem ist, dass ich mit den in meinem Array gespeicherten Werten nicht zurückverfolgen kann.

Zum Beispiel, wenn das Problem das klassische 'Longest Subsequence' Problem ist, kann ich den Wert der längsten Subsequenz erreichen, aber ich bin nicht in der Lage, durch die gespeicherten Werte zurückzuverfolgen und zu finden, welche Buchstaben/Ziffern in der erscheinen Teilfolge.

Ich habe eine Menge Tutorials für Universitätskurse und Youtube-Tutorials durchgearbeitet, aber niemand scheint zu erklären, wie eine Person das Teilproblem richtig "beschreiben" kann.

Hat jemand Tipps, wie man die Teilprobleme herstellen und Array-Werte beibehalten kann, so dass Backtracking möglich und einfach ist?

Answer 1

Eine einfache Lösung besteht darin, ein zweites Array mit den gleichen Abmessungen wie das erste Array beizubehalten und es als index Array zu bezeichnen und es zum Verfolgen der Position des Elements zu verwenden, das zu Ihrer Auswahl beigetragen hat.

So in einem 2d Beispiel:
Lassen A sein die Standard-dynamische Programmierung Array
I den Index Array

sein lassen, wenn der Wert A[x,y] von A[x0,y0] entschieden wird, dann I[x,y]=(x0,y0).

Wenn Sie versuchen, von A[i,j] zurückzurücken, greifen Sie auf I[i,j] zu, um das nächste Element in der Backtrack-Kette zu finden.

Sie können Standardwerte für das Array I verwenden, damit Sie wissen, wann Sie das Ende der Kette erreicht haben.