2705 - 팰린드롬 파티션

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

7을 팰린드롬 파티션으로 표현하면 아래와 같다.

       7
   1+  5  +1
   2+  3  +2
  1+1+ 3 +1+1
  3+   1   +3
1+1+1+ 1 +1+1+1

가운데를 축으로 보고, 양쪽으로 갈라지는 수에 대해 다시 재귀적으로 그것들을 축으로 센다.

아래와 같은 점화식으로 표현 가능하다.
$$f(n) = 1 + f(0) + \dots + f(n/2)$$
1은 자기 자신을 나타내는 가짓 수이기 때문에 매번의 분열마다 더해준다.

#include <bits/stdc++.h>
using namespace std;

int dp[1001];

int f(int n){
    if(n < 1) return 0;
    if(n < 2) return 1;
    
    int& r = dp[n];
    if(r != -1) return r;
    
    r = 1;
    for(int i=0; i<=n/2; ++i){
        r += f(i);
    }
    return r;
}

int main(){
    int n, T;
    scanf("%d", &T);
    memset(dp, -1, sizeof(dp));
    while(T--){
        scanf("%d", &n);
        printf("%d\n", f(n));
    }
    return 0;
}