POJ 3790 Recursively Palindromic Partitions

問題

与えられた自然数を、それ以下の自然数の数列の和で表現する。これを自然数の分割と呼ぶ。回文となるような分割をPalindromic Partitionという。そのうち以下の条件を満たす分割をRecursively Palindromic Partitionsという。
条件：分割の左右それぞれがRecursively Palindromic Partitionsである。ただし分割数1の分割は常にRecursively Palindromic Partitionである。

与えられる自然数のRecursively Palindromic Partitionsの数をもとめよ。

やりかた

分割統治で真ん中から左右に分けていき、分けきれなくなるまでわけられたらひとつと数える。メモ化して計算量を落とす。

以下ソース。

int N;
ll dp[1001][1001];

ll rec(int idx, int rem){
  if(rem == 0) return 1;
  if(dp[idx][rem] != -1) return dp[idx][rem];
  
  ll ret = 0;
  for(int i = 0; i <= rem; i++){
    if((rem - i) % 2) continue;
    ret += rec(idx + 1, (rem - i) / 2);
  }
  return dp[idx][rem] = ret;
}

int main(){
  int T;
  cin >> T;
  for(int i = 1; i <= T; i++){
    cin >> N;
    FILL(dp, -1);
    cout << i << " " << rec(0, N) << endl;
  }
  return 0;
}