Given a positive integer n, find the least number of perfect square numbers (for example,
1, 4, 9, 16, ...) which sum to n.
For example, given n =
12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
Solutions:
Using DP. For many detailed explanation please refer to: https://leetcode.com/discuss/58056/summary-of-different-solutions-bfs-static-and-mathematics
One of trick to use is so called "Static DP", which use a static vector to save already computed results among huge number of test cases to same more time. But for single call, it is no difference to what I present here.
Round 3:
No comments:
Post a Comment