给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 示例 1:
输入: n = 12 输出: 3 解释: 12 = 4 + 4 + 4. 示例 2:
输入: n = 13 输出: 2 解释: 13 = 4 + 9.
思路：对问题建模：将整个问题变成一个图论问题。 从n到0，每个数字代表一个节点;； 如果两个数 x 到 y 相差一个完全平方数，则连接一条边； 我们就得到了一个无权图； 原来的问题就转化为，在这个无权图中找出从 n 到 0 的最短路径，所以需要 BFS 来完成 有人可能会通过贪心算法来处理该问题，但这是错误的，因为我们要找的是最少个数，贪心可能找的是最简单的树，而数量可能会很多。
class Solution { static class Node { int val; int step; public Node(int val, int step) { this.val = val; this.step = step; } } public int numSquares(int n) { Queue<Node> queue = new LinkedList<Node>(); queue.add(new Node(n, 0)); boolean[] visited = new boolean[n + 1]; while (!queue.isEmpty()) { int val = queue.peek().val; int step = queue.peek().step; queue.remove(); for (int i = 1; ; i++) { int newNum = val - i * i; if (newNum < 0) { break; } if (newNum == 0) { return step + 1; } if (!visited[newNum]) { queue.add(new Node(newNum, step + 1)); visited[newNum] = true; } } } return -1; } }