이 코드를 재귀 적에서 반복적으로 변환하십시오. DP

double R(int N, int x[206], int i, int c){ 
    if (memo[i][c] != 0) return memo[i][c]; 

    if (i==N){ 
     if (c>=23) return 1; 
     else return 0; 
    } 

    double s; 
    s = R(N,x,i+1,c+x[i]); 
    s += R(N,x,i+1,c-x[i]); 
    memo[i][c] = s; 
    return s; 
}

지금은 재귀 적으로 메모를 작성한 함수입니다. 가능한 한 반복적 인 동등한 DP로 변환하고 싶습니다. 아니면 내가 할 수있는 유일한 방법인가?이 코드를 재귀 적에서 반복적으로 변환하십시오. DP

출처

2013-08-02 user78793

'goto'와'stack'의 무리는 재귀를 에뮬레이트 할 수 있습니다. – Shivam

x와 상수 N의 내용을 알지 못하면 어렵습니다. – Sylwester

N은 정수로, 최대 206 개까지 갈 수 있습니다. x는 임의의 정수 배열입니다. – user78793

이론적으로 모든 재귀 적 방법을 반복적 방법으로 변환 할 수 있습니다. 그렇습니다.이 코드도 가능합니다.

는이 스레드에 대해 더 많은 : x는 임의의 정수를 포함 할 수 있기 때문에 https://stackoverflow.com/questions/931762/can-every-recursion-be-converted-into-iteration는

출처

2013-08-02 14:54:29

모든 재귀가 변환 될 수 있음을 알고 있지만,이 방법을 묻는 중입니다. 그 말이 맞다면 번역 할 수 있습니다. 영어가 나쁘면 죄송합니다. – user78793

질문의 두 번째 부분에 답했습니다. 그러나 우리가 당신을 위해 모든 일을하기를 원한다면 ... 이것은 문제가 될 수 있습니다. 이 사이트는 "이 문제를 해결하려고 노력했지만 여기에 갇혀 있습니다"라는 것보다 "나를 위해 해결하십시오"에 관한 것입니다. 이미 반복 한 것으로 번역 될 수 있음을 알고 있으므로 이미 수행 한 작업, 특정 문제를 보여줍니다. –

내가 무엇을해야할지 알았다면이 질문을하지 않았을 것입니다. – user78793

, 당신은 정말 i이 고정 c의 어떤 값 R을 계산해야합니다. 일부 코드를 설명하기 :

// case where i == N 
for (int c = INT_MIN; c < INT_MAX; ++c) { 
    memo[N][c] = (c>=23) ? 1 : 0; 
} 

for (int k = N - 1; k >= i; --k) { 
    for (int c_ = INT_MIN; c_ < INT_MAX; ++c_) { 
    memo[k][c_] = memo[k+1][c_ + x[k]] + memo[k+1][c_ - x[k]]; 
    } 
} 
return memo[i][c];

어쩌면 x의 값에 대한 몇 가지 제한 사항이 결과를 개선하는 데 도움이 될 수 있습니다.

출처

2013-08-02 20:59:55 MAnyKey

이 코드를 재귀 적에서 반복적으로 변환하십시오. DP

답변

관련 문제