|
|
back to boardhelp !!!!! Posted by Alibek 29 Feb 2008 19:19 Can anybody explain me DP algo what is it? Re: help !!!!! 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)) |
|
|