Referência para LA 4235 (Luiza)

#include <stdio.h>
#include <string.h>

int dp[1010];
int _42,n;

int doit(int a) {
    if (dp[a]!=-1) return dp[a];
    dp[a]=1;

    for (int i=1; i<=a; i++)
        if (a-2*i>=0)
            dp[a]+=doit(i);

    return dp[a];
}

int main() {
    memset(dp,-1,sizeof(dp));
    dp[0]=1; dp[1]=1;
    scanf("%d", &_42);

    for (int i=0; i<_42; i++) {
        scanf("%d", &n);
        printf("%d %d\n", i+1,doit(n));
    }

    return 0;
}