再帰呼び出しを追跡する最も簡単な方法は？

Question

問題に再帰的なDP解を書きました。解決策はいくつかのテストケースで失敗しています（オーバーカウントまたは1回のアンダーカウント）。最終回答につながった州だけをどのように追跡したり、印刷したりすることができますか？

再帰関数は、このようなものです。それは4つの入力を取ります。前に特定の状態が評価されている場合は、std::mapから解決策を返します。それ以外の場合は、それを評価します。このソリューションは、すべての状態に対して再帰的にminの値を返します。

これはPlay the Dragon

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

を解決しようとする試みである一つの簡単な方法は、Tがあなたのタプルである場合は、std::map <T, std::pair<int, T>>を使用する、すなわち、計算値と一緒にマップ内の親タプルを保つことになります。

Answer 2

私はあなたの希望に応えるソリューションがあると思いますが、それはまったく簡単ではなく、実装することでコードに多くの問題やエラーが導入される可能性があります。正しい答え）。アイデアは、グローバルにどこかに格納された一意のIDとデータを持つ新しい関数呼び出しをマークすることです。関数が呼び出されると、その親IDに関する情報があり、呼び出すすべてのブランチに渡すための独自のIDを作成する必要があります。終了すると、そのIDを親IDデータセルに書き込みます。ブランチングのための関数には、2つのカウントの最小値を計算するときに、1つの場所しかありません。したがって、親IDデータセルに、両方の呼び出し結果を将来のanalasysで比較するIDで指定する必要があります。したがって、あなた自身の上で有益ではない呼び出しの構造を作成します。主なものは、親のIDにいくつかの追加情報を追加することです - どのブランチが選択されたのですか（私はあなたに15のリターンステートメントと2つの選択肢があります。選択したブランチに対して、あなたとIDフィールドの選択フラグ。このフラグによって、計算が終了するとIDからIDへとデータが移動し、画面には「選択された」ものだけがデータを呼び出すようになります。がんばろう！