题目
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.
解法思路（一）
数学建模
- 构建 n 个节点的有向无权图，如果 y 到 x 之间差了一个完全平方数，就添加一条由 y 指向 x 的边；
- 求 n 最少由几个完全平方数构成，就是求节点 n 到 0 的最短路径；
构建的图
构建的图.jpg
算法过程手绘
算法过程手绘_279.jpg
广度优先遍历（BFS）
- 一般的广度优先遍历，是先将图加载到内存中，然后对图以标定点开始进行广度优先遍历，从而知道了所有点到标定点的最短路径；
- 对这个问题，数学建模出来的图，不会先被加载到内存，然后从 0 开始广度优先遍历（BFS），继而求出 n 到 0 的最短路径；
- 对这个问题，由于图没有事先加载到内存中，就要从末端（节点 n）以最短的路径回溯到标定点 0，还好，图的构建规则是知道的，这让以末端（节点 n）为起点以最短路径回溯到标定点是有可能的；根据图的构成规则（如果 y 到 x 之间差了一个完全平方数，就添加一条由 y 指向 x 的边），可以知道末端（节点 n）的邻点，并且知道到末端（节点 n）的距离，把邻点和距离组装成一对，排入队列，这就相当于从末端（节点 n）开始的层序遍历（广度优先遍历 BFS），每次从队列中移出同一层的节点，都能知道下一层的节点，并把下一层的节点和距末端（节点 n）的距离组成一队，压入队列，直到第一次遇见节点为 0 的对， 意味着某一层的某个节点相邻于节点 0，并且这个对中存的距离，就是由层序遍历得到的，末端（节点 n）到节点 0 的最短路径，就是组成数字 n 的最少的完全平方数的个数；
小发现
- 从标定点广度优先遍历可以得到标定点到其余所有点的最短路径，那么从任何一点开始广度优先遍历也可以得到其到标定点的最短路径不是吗？
解法实现（一）
时间复杂度
- O(n)；
空间复杂度
- O(n)；
关键字
数学建模 广度优先遍历
实现细节
- 如果数组的元素个数是 n，就开辟 n 个长度的空间，那么 n 从索引的角度看，就指向了数组最后一个元素的后面（0-Based），属于数组的外面；
- 如果数组的元素个数是 n，就开辟 n+1 个长度的空间，那么 n 从索引的角度看，指向数组最后一个元素（1-Based）；
import java.util.LinkedList;
import javafx.util.Pair;
public class Solution2 {
public int numSquares(int n) {
LinkedList<Pair<Integer, Integer>> queue = new LinkedList<Pair<Integer, Integer>>();
queue.addLast(new Pair<Integer, Integer>(n, 0));
boolean[] visited = new boolean[n+1];
visited[n] = true;
while(!queue.isEmpty()){
Pair<Integer, Integer> front = queue.removeFirst();
int num = front.getKey();
int step = front.getValue();
if(num == 0)
return step;
for(int i = 1 ; num - i*i >= 0 ; i ++)
// 如果邻点还没被加入队列
if(!visited[num - i * i]){
queue.addLast(new Pair(num - i * i, step + 1));
visited[num - i * i] = true;
}
}
throw new IllegalStateException("No Solution.");
}
public static void main(String[] args) {
System.out.println((new Solution2()).numSquares(12));
System.out.println((new Solution2()).numSquares(13));
}
}
