29. 完全平方数

题目

解析

• 类型：BFS

• 步骤：

1. 首先，把要求的数分为多个数相加，比如：10 = 1 + 9 = 1 + 4 + 4 + 1 = 1 + 1 + …… + 1
2. 但是，由于使用的循环，所以肯定是1 + 9先出现
3. 所以，依次类推，直到找到要求的数

• PS：
  1. BFS就是一层找一层，找到的肯定是最近的；
  2. 比如：4就是 0 + 4，只有一个数，设为第一层；同理，9 = 0 + 9，也只有一个数，同样为第一层
  3. 当遍历完0后，开始遍历第一层的数，那么找到的就是两个数的，即为第二层
  4. 依次类推

代码

int numSquares(int n) {
    queue<int> q;
    q.push(0);
    vector<int> dist(n + 1, INT_MAX);
    dist[0] = 0;
    while(q.size()) {
        int t = q.front();
        q.pop();
        if(t == n) {
            return dist[t];
        }
        for(int i = 1; i * i + t <= n; i++) {
            int j = i * i + t;
            if(dist[j] > dist[t] + 1) {
                dist[j] = dist[t] + 1;
                q.push(j);
            }
        }
    }
    return 0;
}