무차별의 동적 프로그래밍 감소

Question

이모티콘은 두 세미콜론 사이의 임의의 양수의 밑줄로 구성됩니다. 따라서 가능한 가장 짧은 이모티콘은 ;_;입니다. ;__; 및 ;_____________; 문자열도 유효한 이모티콘입니다.

주어진 문자열은 (;, _)입니다. 문제는 문자열을 하나 이상의 이모티콘으로 나눠서 가능한 나누기 수를 계산하는 것입니다. 각 이모티콘은 메시지의 하위 시퀀스 여야하며 메시지의 각 문자는 정확히 하나의 이모티콘에 속해야합니다. 서브 시퀀스는 인접하지 않아도됩니다. subsequence definition. n이 큰 경우

이

countDivision(string s){ 
//base cases 
if(s.empty()) return 1; 
if(s.length()<=3){ 
    if(s.length()!=3) return 0; 
    return s[0]==';' && s[1]=='_' && s[2]==';'; 
} 
    result=0; 
//subproblems 
    genrate all valid emocticon and remove it from s let it be w 
    result+=countDivision(w); 
    return result; 
} 

이 솔루션은 위의 쉽게 내가이 짐승을 변환하는 방식의 어떤 종류를 사용해야합니다 같은 100 시간 종료됩니다

내가 생각 접근 방식은 다음과 같이 재귀 적 방법을 작성하는 것입니다 다이나믹 프로그래밍 솔루션에 대한 강력한 해결책?

몇몇 예

1. ";_;;_____;" ans is 2 
2. ";;;___;;;" ans is 36 

Example 1. 

";_;;_____;" Returns: 2 
There are two ways to divide this string into two emoticons. 
One looks as follows: ;_;|;_____; and the other looks like 
this(rembember we can pick subsequence it need not be contigous): ;_ ;|; _____; 

I는 (N^4) - 시간을 오 설명하고 (즉 쉽게 단지 O (N^3) 공간을 사용하여 개선 될 수있다) 동적 프로그래밍 솔루션 - 공간 것이다

Answer 1

그 n = 100 정도까지 작동해야합니다.

;으로 구성된 경우 "신선한"하위 시퀀스를 호출합니다.

이모티콘에 해당하는 경우 "finished"하위 시퀀스를 호출합니다.

길이가 0이 아니며 이모티콘의 적절한 접두어 인 경우 부분 시퀀스 "partial"을 호출합니다. (빈 문자열, _, ;; 및 ;___;;가없는 동안 그래서 예를 들어, ;, ;_ 및 ;___ 부분 시퀀스는, 모두.)는 신선한 완료 또는 일부의 경우

마지막으로, "허용"서브 순서를 호출 .

문자열의 처음 i 문자를 정확하게 j + k + m 개의 허용 가능한 서브 시퀀스로 분할하는 방법의 수를 f (i, j, k, m)로하고, 그 중 j은 신선하고, k는 부분적이며 m 완료되었습니다. 이모티콘에 유효한 파티션의 접두사가 있으면 i, j, k 및 m이 고유하게 결정됩니다. 이는 유효한 파티션의 접두어가 둘 이상의 튜플 (i, j, k, m)에 의해 계산되지 않음을 의미하므로 if 우리는 각 튜플 (i, j, k, m)에 대해 내의 내에서 튜플이 모두 한 번만 계산된다는 것을 보장 할 수 있습니다. 그러면 합계를 얻기 위해 튜플에 대한 개수를 더할 수 있습니다. 구체적으로, 질문에 대한 대답은 f (n, 0, j, 0) 중 하나 인 < = j < = n에 대한 합계가됩니다.

If s[i] = "_": 
    f(i, j, k, m) = 
    (j+1) * f(i-1, j+1, k, m-1) // Convert any of the j+1 fresh subsequences to partial 
    + m * f(i-1, j, k, m)   // Add _ to any of the m partial subsequences 

Else if s[i] = ";": 
    f(i, j, k, m) = 
    f(i-1, j-1, k, m)    // Start a fresh subsequence 
    + (m+1) * f(i-1, j, k-1, m+1) // Finish any of the m+1 partial subsequences 

우리는 또한

f(0, 0, 0, 0) = 1 
f(0, _, _, _) = 0 
f(i, j, k, m) = 0 if any of i, j, k or m are negative 

내 자신의 C++ 구현이 몇 밀리 초 단위로 ;;;___;;; 36의 정답을 제공하고, 예를 들어, 기본 케이스가 필요합니다 ;;;___;;;_;_;에 대한 답변은 540 (몇 밀리 초)입니다. 66 ; 다음에 66 _이오고이 이어지는 문자열의 경우 2 초 미만이며 0 응답을 보냅니다 (아마도 long long의 오버플로로 인한 것임).

Answer 2

다음은 66 ; s의 문자열에 대한 응답을 즉시 반환하고 66 _을 입력 한 다음 66 ;을 입력하는 매우 간단한 메모 재귀입니다. 이 함수에는 i = index in the string, j = number of accumulating emoticons with only a left semi-colon 및 k = number of accumulating emoticons with a left semi-colon and one or more underscores의 세 가지 매개 변수가 있습니다.

배열은 각 색인의 오른쪽에서 사용할 수있는 밑줄과 세미콜론의 수에 따라 구성되어 다음 가능성을 결정하는 데 도움이됩니다.

복잡성 O(n^3)하고 j이 n/4 대부분에서 최대 n/2 및 k을 여기서 문제는, 검색 공간을 제한. 이 명확 있도록

var s = ';_;;__;_;;'; 
 

 
// record the number of semi-colons and 
 
// underscores to the right of each index 
 
var cs = new Array(s.length); 
 
cs.push(0); 
 

 
var us = new Array(s.length); 
 
us.push(0); 
 

 
for (var i=s.length-1; i>=0; i--){ 
 
    if (s[i] == ';'){ 
 
    cs[i] = cs[i+1] + 1; 
 
    us[i] = us[i+1]; 
 
    
 
    } else { 
 
    us[i] = us[i+1] + 1; 
 
    cs[i] = cs[i+1]; 
 
    } 
 
} 
 

 
// memoize 
 
var h = {}; 
 

 
function f(i,j,k){ 
 
    // memoization 
 
    var key = [i,j,k].join(','); 
 

 
    if (h[key] !== undefined){ 
 
    return h[key]; 
 
    } 
 

 
    // base case 
 
    if (i == s.length){ 
 
    return 1; 
 
    } 
 

 
    var a = 0, 
 
     b = 0; 
 
    
 
    if (s[i] == ';'){ 
 
    // if there are still enough colons to start an emoticon 
 
    if (cs[i] > j + k){ 
 
     // start a new emoticon 
 
     a = f(i+1,j+1,k); 
 
    } 
 
     
 
    // close any of k partial emoticons 
 
    if (k > 0){ 
 
     b = k * f(i+1,j,k-1); 
 
    } 
 
    } 
 
    
 
    if (s[i] == '_'){ 
 
    // if there are still extra underscores 
 
    if (j < us[i] && k > 0){ 
 
     // apply them to partial emoticons 
 
     a = k * f(i+1,j,k); 
 
    } 
 
    
 
    // convert started emoticons to partial 
 
    if (j > 0){ 
 
     b = j * f(i+1,j-1,k+1); 
 
    } 
 
    } 
 
    
 
    return h[key] = a + b; 
 
} 
 

 
console.log(f(0,0,0)); // 52