재귀 호출을 추적하는 가장 쉬운 방법은 무엇입니까?

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를 씁니다. 분기 계산을 할 때 함수 계산에 두 자리 수를 계산할 때 함수가 하나만 있습니다. 따라서 부모 ID 데이터 셀에 두 개의 호출 결과를 모두 넣어야합니다. 이후의 analasys에서 비교할 ID가 필요합니다. 따라서 당신은 자신의 것으로 유익하지 않은 호출 구조를 생성합니다. 가장 중요한 것은 상위 ID에 몇 가지 추가 정보를 추가하는 것입니다. 어떤 분기가 선택되었는지 (내 경우에는 15 개의 return 문과 선택 항목 2 개가 포함되어 있습니다. 무엇이 선택되었는지 알고 싶습니다). 선택한 지사에 대해 당신과 이드 필드는 선택한 플래그를 사용합니다. 이 플래그로 계산이 끝나면 ID에서 ID로 이동하여 데이터를 쓰고 "선택"된 데이터 만 화면에 씁니다. 행운을 빕니다!