LA 3516 - Exploring Pyramids

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1517
오래간만의 트리 dp
dp[l][r]는 l에서 r 사이의 문자열로 형성된 서브트리가 몇 가지인지 나타낸다
그리고 가장 왼쪽 나뭇가지의 위치를 일일이 열거하고 i라고 가정하면 l+1에서 i-1로 돌아가는 것이 가장 왼쪽 나뭇가지의 종류이고 나머지 부분을 곱한다
나머지 부분 i에서 r는 가장 왼쪽 나뭇가지를 제거한 또 하나의 자목으로 귀속되면 된다
코드:

#include <iostream>

#include <cstdio>

#include <string>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <queue>



#define ll long long

using namespace std;



const ll MOD= 1000000000;

const int N=305;

ll dp[N][N];

char s[N];

ll dfs(int l,int r)

{

    if(dp[l][r]!=-1)

    return dp[l][r];

    if(l>r)

    return (dp[l][r]=0);

    if(l==r)

    return (dp[l][r]=1);

    if(s[l]!=s[r])

    return (dp[l][r]=0);

    dp[l][r]=0;

    for(int i=l+1;i<=r;++i)

    if(s[i]==s[l])

    dp[l][r]=(dp[l][r]+dfs(l+1,i-1)*dfs(i,r))%MOD;

    return dp[l][r];

}

int main()

{

    //freopen("data.in","r",stdin);

    while(scanf("%s",s)!=EOF)

    {

        int n=strlen(s);

        memset(dp,-1,sizeof(dp));

        cout<<dfs(0,n-1)<<endl;

    }

    return 0;

}