The correct, optimal and working solution for programming question NFURY on spoj

#include<stdio.h> int main() { int a[32]={1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289,324,361,400,441,484,529,576,625,676,729,784,841,900,961}; int i,t,j; int dp[1005]; dp[1]=1; dp[2]=2; dp[3]=3; for(i=4;i<=1000;i++) { dp[i]=i; for(j=0;j<31;j++) { if(a[j]<=i && dp[i]>dp[i-a[j]]+1) dp[i]=dp[i-a[j]]+1; } } scanf("%d",&t); while(t--) { int n; scanf("%d",&n); printf("%d\n",dp[n]); } return 0; }