Der einfachste Weg, rekursive Aufrufe zu verfolgen?

Question

Ich schrieb eine rekursive DP-Lösung für ein Problem. Die Lösung schlägt bei einigen Testfällen fehl (es wird nur eine einzige Umdrehung zu viel oder zu wenig gezählt). Wie kann ich nur die Status rückverfolgen oder drucken, die zu meiner endgültigen Antwort geführt haben?

Die rekursive Funktion ist so etwas. Es dauert 4 Eingänge. Wenn ein bestimmter Zustand zuvor ausgewertet wurde, gibt er die Lösung von std::map zurück, andernfalls wertet er ihn aus. Die Lösung gibt den Wert min für jeden Status rekursiv zurück.

Dies ist ein Versuch Play the Dragon von Google CodeJam 2017 1A

int hd,ad,hk,ak,b,d; 
int inf=1e9+1; 
map< tuple<int,int,int,int>, int > dp; 

int count(int hld, int hlk, int atd, int atk){ 
    if(dp[make_tuple(hld,hlk,atd,atk)]){ 
    return dp[make_tuple(hld,hlk,atd,atk)]; 
    } 
    else{ 
    if(hlk<=0){ 
     return 0; 
    } 
    if(hld<=0){ 
     return inf; 
    } 
    if(hlk-atd<=0){ 
     return 1; 
    } 
    if(hld==hd-atk){ 
     if(b==0||d==0){ 
     if(b==0&&d!=0){ 
      return dp[make_tuple(hld,hlk,atd,atk)] = 1 + min(
                  count(hld-atk,hlk-atd,atd,atk), 
                  count(hld-atk+d,hlk,atd,(atk-d)<0?0:(atk-d)) 
                  ); 
     } 
     if(b!=0&&d==0){ 
      return dp[make_tuple(hld,hlk,atd,atk)] = 1 + min(
                  count(hld-atk,hlk-atd,atd,atk), 
                  count(hld-atk,hlk,atd+b,atk) 
                  ); 
     } 
     return dp[make_tuple(hld,hlk,atd,atk)] = 1 + count(hld-atk,hlk-atd,atd,atk); 
     } 
     return dp[make_tuple(hld,hlk,atd,atk)] = 1 + min(
                 count(hld-atk,hlk-atd,atd,atk), 
                 min(
                  count(hld-atk,hlk,atd+b,atk), 
                  count(hld-atk+d,hlk,atd,(atk-d)<0?0:(atk-d)) 
                  ) 
                 ); 
    } 
    if(b==0||d==0){ 
     if(b==0&&d!=0){ 
     if(atk<=0){ 
      return dp[make_tuple(hld,hlk,atd,atk)] = 1 + count(hld-atk,hlk-atd,atd,atk); 
     } 
     return dp[make_tuple(hld,hlk,atd,atk)] = 1 + min(
                 count(hld-atk,hlk-atd,atd,atk), 
                 min(
                  count(hd-atk,hlk,atd,atk), 
                  count(hld-atk+d,hlk,atd,(atk-d)<0?0:(atk-d)) 
                  ) 
                 ); 
     } 
     if(b!=0&&d==0){ 
     return dp[make_tuple(hld,hlk,atd,atk)] = 1 + min(
                 count(hld-atk,hlk-atd,atd,atk), 
                 min(
                  count(hld-atk,hlk,atd+b,atk), 
                  count(hd-atk,hlk,atd,atk) 
                  ) 
                 ); 
     } 
     if(atk<=0){ 
     return dp[make_tuple(hld,hlk,atd,atk)] = 1 + count(hld-atk,hlk-atd,atd,atk); 
     } 
     return dp[make_tuple(hld,hlk,atd,atk)] = 1 + min(
                 count(hld-atk,hlk-atd,atd,atk), 
                 count(hd-atk,hlk,atd,atk) 
                 ); 
    } 

    if(atk<=0){ 
     return dp[make_tuple(hld,hlk,atd,atk)] = 1 + min(
                 count(hld-atk,hlk-atd,atd,atk), 
                 count(hld-atk,hlk,atd+b,atk) 
                 ); 
    } 
    return dp[make_tuple(hld,hlk,atd,atk)] = 1 + min(
                count(hld-atk,hlk-atd,atd,atk), 
                min(
                 count(hld-atk,hlk,atd+b,atk), 
                 min(
                  count(hd-atk,hlk,atd,atk), 
                  count(hld-(atk-d)<0?0:(atk-d),hlk,atd,(atk-d)<0?0:(atk-d)) 
                 ) 
                 ) 
                ); 
    } 
} 

Answer 1

Eine einfache Methode, um die Eltern Tupel in der Karte zu lösen zusammen mit dem berechneten Wert würde zu halten, das heißt, wenn T Ihr Tupel Sie std::map <T, std::pair<int, T>> verwenden.

Answer 2

Ich denke, dass es eine Lösung für Ihren Wunsch geben kann, aber es ist überhaupt nicht einfach und Sie können mehr Probleme oder Fehler in Ihren Code einführen als jetzt (ich schlage ihre Anwesenheit vor, weil Sie nicht das erreichen richtige Antwort). Die Idee ist, jeden neuen Funktionsaufruf mit einer eindeutigen ID und Daten zu markieren, die irgendwo auf der Welt gespeichert sind. Wenn die Funktion aufgerufen wird, sollte sie Informationen über ihre Eltern-ID enthalten und eine eigene ID erstellen, die an alle Zweige übergeben wird, die sie aufruft. Wenn es fertig ist, schreibt es seine ID in die Eltern-ID-Datenzelle mit dem Ergebnis. Sie haben nur einen Platz in Ihren Funktionen für die Verzweigung - wenn Sie min von zwei Zählungen berechnen. Also müssen Sie in die Eltern-ID-Datenzelle beide Anrufergebnisse mit IDs eingeben, um sie in zukünftigen analasys zu vergleichen. So erstellen Sie eine Struktur von Aufrufen, die für sich allein nicht informativ ist. Die Hauptsache ist, zu Eltern-ID einige zusätzliche Informationen hinzuzufügen - die Niederlassung gewählt wurde (I meand, Sie haben 15 return-Anweisungen und zwei Varianten von Entscheidungen in ihnen - ich glaube, Sie wissen wollen, was gewählt wurde). Für jeden gewählten Zweig haben Sie und das ID-Feld ausgewählt. Mit diesem Flag werden Sie, wenn Ihre Berechnung beendet ist, von ID zu ID gehen und Ihre Daten schreiben und nur ausgewählte Anrufdaten auf den Bildschirm schreiben. Viel Glück!