a,b,c의 조합으로 이루어진 문자열에서 aaa..bb...c.. 형태의 조합의 갯수

우선 DP로 풀이 가능할 듯.

int countnumber(string &s, int curr, int it){

if(curr==s.size()) return 0;

// go through

int ret = 0;

for(int i = curr ; i < s.size() ; i++){

if(s[i]==it+'a'){

ret += countnumber(s,i+1,it);

}else if(it!=2&&s[i]==it+'a'+1){

ret += countnumber(s,i+1,it+1);

}

}

return ret;

}

" 매 위치의 것을 포함하는 " 갯수를 세기 때문에, 섭문제의 합이 중복을 가지지 않는다 !!!

경우의 수를 DP로 셀때는 특히 현재 위치에서 아예 새로운 조합을 만들어내는지 잘 확인해야 한다.

시간 복잡도 : O(N^2)

다른 풀이법 ( 최적화된 선계산법 )

아예 "갯수를 세는" 과정 자체가 DP 가 하는건데, DP 자체를 선계산 해버릴 수 있다.

If current character is ‘a’, then there are following possibilities :
    a) Current character begins a new subsequence.
    b) Current character is part of aCount subsequences.
    c) Current character is not part of aCount subsequences.
    Therefore we do aCount = (1 + 2 * aCount);

    If current character is ‘b’, then there are following possibilities :
    a) Current character begins a new subsequence of b’s with aCount subsequences.
    b) Current character is part of bCount subsequences.
    c) Current character is not part of bCount subsequences.
    Therefore we do bCount = (aCount + 2 * bCount);

    If current character is ‘c’, then there are following possibilities :
    a) Current character begins a new subsequence of c’s with bCount subsequences.
    b) Current character is part of cCount subsequences.
    c) Current character is not part of cCount subsequences.
    Therefore we do cCount = (bCount + 2 * cCount);

O(N) 이란다. ㅋㅋ 그냥 경우의 수 계산을 손으로 한 풀이인듯