簡單的方法來跟蹤遞歸調用？

-1

我爲一個問題寫了一個遞歸DP解決方案。這個解決方案對於一些測試案例來說是失敗的（它只是一次過度計數或者計數不足）。我如何才能引用或打印那些導致我最終答案的國家？簡單的方法來跟蹤遞歸調用？

的遞歸函數是這樣的。它需要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)) 
                 ) 
                 ) 
                ); 
    } 
}

來源

2017-04-20 Chirag Arora

一個簡單的方法將保持在地圖父元組的計算值，即，如果T是你的元組使用std::map <T, std::pair<int, T>>一起企圖。

來源

2017-04-20 08:23:50

我覺得有可能是你的願望的解決方案，但它不是簡單的在所有和實現它，你可以介紹你的代碼比現在有更多的問題或錯誤（我建議他們的存在，因爲你沒有達到正確答案）。這個想法是標記任何新的函數調用與唯一的ID和數據存儲在全球的某個地方。當函數被調用時，它應該有關於它的父id的信息並且創建自己的id來傳遞給它要調用的所有分支。當它完成後，將她的ID寫入父ID號數據單元中。在分支功能中，只有一個位置 - 計算兩個計數的最小值時。所以你需要把父母身份數據單元格中的兩個結果與id在未來的analasys中進行比較。因此你創建了一個獨立的呼叫結構，根本沒有信息。最重要的是添加到父母id一些額外的信息 - 哪個分支被選中（我meand，你有15個回報陳述和2個變種內的選擇 - 我想你想知道選擇什麼）。對於任何選擇的分支你和ID字段選擇標誌。通過這個標誌，當你的計算完成時，你將從id到id thothht你的數據，並在屏幕上只寫「選擇」的數據。祝你好運！

來源

2017-04-20 08:24:07

簡單的方法來跟蹤遞歸調用？

回答

相關問題