[BOJ/백준][Gold3] 14505 : 팰린드롬 개수 구하기 (Small) (C++)

https://www.acmicpc.net/problem/14505

14505번: 팰린드롬 개수 구하기 (Small)

 

[난이도] Gold3
[유형] DP

[풀이]
['abb' 의 부분수열은 {'a'}, {'b'}, {'b'}, {'ab'}, {'ab'}, {'bb'}, {'abb'}]
지문의 위 부분을 잘 봐야 합니다. 'ab'가 두번 나오기 때문에 부분수열은 연속된 수들이 아니어도 됩니다.

연속이 아니어도 아래와 같은 점화식의 DP로 해결이 가능합니다.
DP[l][r] = DP[l+1][r]+DP[l][r-1]-DP[l+1][r-1] (s[l]!=s[r])
           DP[l+1][r]+DP[l][r-1]+1 (s[l]==s[r])

s[l]!=s[r] 일때 DP[l+1][r-1]을 빼주는 이유는 DP[l+1][r],DP[l][r-1] 에 모두 DP[l+1][r-1]가
포함되어 있기 때문에 중복되지 않도록 빼주는 것입니다.

반면 s[l]==s[r] 일 때는 양 끝에 s[l],s[r]을 붙임으로써 DP[l+1][r-1]만큼이 그대로 더해지므로
빼지 않아도 되며, 부분수열 {s[l],s[r]}인 경우를 추가해야 하므로 1을 더해주었습니다.

 

#include <string>
#include <iostream>
#include <cstring>
using namespace std;
string s;
int dp[31][31];
int sol(int l,int r){
    if(l==r) return 1;
    if(l>r) return 0;
    int& ret=dp[l][r];
    if(ret!=-1) return ret;
    ret = sol(l+1,r)+sol(l,r-1);
    if(s[l]!=s[r]) ret-=sol(l+1,r-1); 
    else ret++;
    return ret; 
}
int main(){
    cin >> s;
    memset(dp,-1,sizeof(dp));
    cout << sol(0,s.size()-1);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/14505.cpp