ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1073. Square Country

help !!!!!
Posted by Alibek 29 Feb 2008 19:19
Can anybody explain me DP algo what is it?
Re: help !!!!!
Posted by Alexander (201 - P TNU) 12 Mar 2008 22:09
It is easy
At first you should create array of squares[], where ith element equals i*i. This array is key to the desicion)

At start dp[] array has  not improved values(obviously dp[i] = i)
(dp[i] is minimal number of squares that in sum equal to i)
then at every cycle add a new square and
try to improve the previous result of dp.
result in - dp[n]. complexity is O(n*sqrt(n))