Find the Least Number Sums of Perfect Squares
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
Input: n = 12
Explanation: 12 = 4 + 4 + 4.
Input: n = 13
Explanation: 13 = 4 + 9.
Mathematically proven that we need at most up to 4 perfect squares that can be sum up to any positive integers. We also known in this post that we can use Dynamic programming to compute the least number of perfect square numbers that sum up to n.
The DP equation is:
f(0) = 0 f(i) = min(f(i), f(i - j * j); // for j * j <= i
To print which perfect square numbers are summing up to N, we can use another array to record the last perfect square and then keep tracking back last perfect squares until nothing remained. This works because of the inherent Dynamic Programming characteristics - the sub problems are also optimial.
The following Python solution prints the solution to the least number of perfect square sums, for example: 1234 = sqr(3) + sqr(35).
def computeMinSquare(N): M = 100000 # marks as not-visited ans = [M] * (N+1) last = * (N+1) ans = -1 for i in range(1, N+1): for j in range(i): if (i >= j * j) and ans[i - j*j] != M and (ans[i] > ans[i-j*j]+1): last[i] = j # remember the perfect square ans[i] = min(ans[i], ans[i - j * j] + 1) # DP Equation s =  j = N while (j > 0) and (last[j] > 0): a = last[j] s.append("sqr("+str(a) + ")") j = j - last[j]*last[j] print(str(N) + " = " + " + ".join(s)) # prints 1234 = sqr(3) + sqr(35) computeMinSquare(1234)
--EOF (The Ultimate Computing & Technology Blog) --
Reposted to Computing Technology
Every little helps! I hope this helps!
If you like my work, please consider voting for me or Buy Me a Coffee, thanks!
https://steemit.com/~witnesses type in justyy and click VOTE
Alternatively, you could proxy to me if you are too lazy to vote!
Also: you can vote me at the tool I made: https://steemyy.com/witness-voting/?witness=justyy