다음 C++ 코드에 memoisation하는 방법

Question

사실 나는 SPOJ 문제를 해결하기 위해 노력하고 있습니다. [SPOJ] http://www.spoj.com/problems/SQRBR/. 나는 그것을 해결하기 위해 재발을 생각해 냈지만 나는 memoisation을하는 방법을 얻지 못하고있다. 주어진 문제에 대한 암기 방법에 대한 제안이 도움이 될 것입니다. 내 코드는 정답을주고 있지만, 내 코드는 여기에있다. 내 코드 :

#include <iostream> 
#include <cstdio> 

using namespace std; 

void balancedParen(int n, int open, int position, int close, char str[], string s, long long int &counter) { 
if(close == n) { 
    str[pos] = '\0'; 
    printf("%s\n", str); 
    counter++; 
    return; 
} 

if(s[position] == '(') { 
    if(open <= n-1) { 
    str[position] = '('; 
    balancedParen(n, open+1, position+1, close, str, s, counter); 
    } 
} else { 
    if(open < n) { 
    str[position] = '('; 
    balancedParen(n, open+1, position+1, close, str, s, counter); 
    } 
    if(open > close) { 
    str[position] = ')'; 
    balancedParen(n, open, position+1, close+1, str, s, counter); 
    } 
} 
    return ; 
} 

int main() { 
     int a[100], n, k, i; 
     long long counter = 0; 
     int testCases; 

     scanf("%d", &testCases); 

     while(testCases--) { 
       scanf("%d", &n); 
       scanf("%d", &k); 
       char str[100]; 
       string s = ".........................................................................."; 
     for(i = 0; i < k; i++) { 
       scanf("%d", &a[i]); 
       s[a[i]-1] = '('; 
     } 
     balancedParen(n, 0, 0, 0, str, s, counter); 
     printf("%lld\n", counter); 
     counter = 0; 
    } 
    return 0; 
} 

Answer 1

나는 비교적 간단하고 중요한 최적화를 생각할 수있다.

먼저 "카운터"를 참조로 만드는 대신 함수의 반환 값으로 만듭니다. 날 좀 들어라.

이제 주어진 위치가 "1, 7, 15"이라고 말하면됩니다. 재귀 적으로 "1, 2, 3, 4, 5, 6, 7"로가는 대신, 조금 까다로워서 한 단계로 7 단계로 넘어갈 수 있습니다.

예 그냥 개방 괄호 모든 가능한 번호 1 내지 7로 이동하는 데 사용할 수있는 순열의 수를 카운트 할 필요

(이 경우, 3, 4, 5, 6)

1과 7 사이에 3 개의 괄호가있는 방법은 여러 가지가 있습니까?

[[[]]] 
[[][]] 
[][][] 
[[]][] 
[][[]] 

5 순열 (내가 빠뜨린 경우를 제외하고). 그래서 당신은 결과에 5*balancedParen(n, open+3, position+6, close+3, str, s, counter)을 추가 할 수 있습니다. 그리고 4, 5, 6 개 개방 괄호에 대해서도 비슷한 일을하십시오.

당연히 숫자 "5"를 찾는 또 다른 함수를 작성해야합니다 (재귀 적 접근이 가장 단순한 것처럼 보일 것입니다). 그러나 이점은 총 함수 호출 수가 (calls to get from 1 to 7) * (calls to get from 7 to 15)이 아닌 (calls to get from 1 to 7) + (calls to get from 7 to 15)입니다. 여기

내가 설명 된 알고리즘을 사용하여 작동합니다 일부 코드입니다 : 내가 어딘가에 버그가있을 수 있습니다

int countPermutations(int unclosed, int length, int toOpen) 
{ 
    if (toOpen > length) // impossible to open this many, not enough length 
     return 0; 
    int toClose = length-toOpen; 
    if (toClose - toOpen > unclosed) 
     return 0; // No possibilities; not enough open parens to fill the length 
    if (toOpen == 0 || toOpen == length) 
     return 1; // Only one possibility now 
    int ret = 0; 
    if (toOpen > 0) // Count permutations if we opened a paren here 
     ret += countPermutations(unclosed+1, length-1, toOpen-1); 
    if (unclosed > 0) // Count permutations if we closed a paren here 
     ret += countPermutations(unclosed-1, length-1, toOpen); 
    return ret; 
} 

int countNLengthSolutions(int n, int unclosed, int position, int *positions, int remainingPositions) 
{ 
    if (n % 2 != 0) 
     return 0; // must be a length divisible by 2 
    if (position > n) 
     return 0; 
    if (n-position < unclosed) 
     return 0; // too many open parens, no way to complete within length 

    if (remainingPositions == 0) 
    { 
     // Too many open parens to close by the time we get to length N? 
     if ((n - position) < unclosed) 
      return 0; 
     else // Say we have 4 open and a length of 10 to fill; we want (10-4)/2 = 3 more open parens. 
      return countPermutations(unclosed, n-position, (n-position - unclosed)/2); 
    } 
    else 
    { 
     int ret = 0; 
     int toFill = *positions - position - 1; 
     for (int openParens = 0; openParens <= toFill; openParens++) 
     { 
      int permutations = countPermutations(unclosed, toFill, openParens); 
      if (permutations > 0) 
       ret += permutations*countNLengthSolutions(n, unclosed+(2*openParens-toFill)+1, position+toFill+1, positions+1, remainingPositions-1); 
     } 
     return ret; 
    } 
} 

을 정말 확인하는 시간을 소요하지 않았다, 그러나 나는 모든 작동 확인 샘플 입력.