ACM 1073. Square Country / Квадратная страна

 We will keep an array of answers DP[N] where DP[i] shows the answer for i. We also would like to keep a list of squares up to 60000. The algorithm pretty much looks like the algorithm of the knapsack problem except here we keep the number of elements. Initially all the numbers equal to infinity (to a very big number) now starting form 0, if we are on a current element I then we need to check for all the I+ squares and check if we can update the answers, in other words DP[I+squares]=min(DP[i+square], DP[i]+1);

       FULL SOURCE CODE