LeetCode #: 279
Difficulty: Medium
Topics: Math, Dynamic Programming, Breadth-first Search.
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
Example 1:
Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.
Example 2:
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.
The solution uses the Lagrange's four-square theorem.
Reference: Summary of 4 different solutions (BFS, DP, static DP and mathematics) by zhukov