求给定数等于最少的几个完全平方数之和

qieguo 发表于 2015-8-3 15:15
我在想贪心为什么不对呢？我试着举例发现贪心结果没错 但是也没办法去验证

可以参考 http://stackoverflow.com/questio ... -for-some-coin-sets

But for some coin sets, there are sums for which the greedy algorithm fails. For example, for the set {1, 15, 25} and the sum 30, the greedy algorithm first chooses 25, leaving a remainder of 5, and then five 1s for a total of six coins. But the solution with the minimal number of coins is to choose 15 twice.

今天google面试碰到了这个题，应该是bar raiser，
可以用一个hashmap<Integer,List<Integer>> 来保留中间结果，
如果知道最大不会超过4的话，可以考虑用下面的优化：
<0,{}>
然后把所有比N小的平方和先put到这个map里
<1, {1}>
<4,{2}>
<9,{3}>
...
如果想要更优的话，把两个平方和也放进去
<2, {1,1}>
<5, {1,2}>
....
之后带着这个map递归

对于每个n，如果map.containsKey(n)，直接返回map.get(n)
否则 for (i = sqrt(n); i>= 1; i--)  {  找到最小的 min(（1 + size(find(n - i *i)))）)}
...