Если задано положительное целое число n, найдите наименьшее число совершенных чисел (например, 1, 4, 9, 16, ...), сумма которых равна n.
Пример 1:
Вход: n = 12 Выход: 3 Объяснение: 12 = 4 + 4 + 4.
Пример 2:
Вход: n = 13 Выход: 2 Объяснение: 13 = 4 + 9.
import java.util.*;
public class Solution {
public int numSquares(int n) {
int i = 1;
int ret = Integer.MAX_VALUE;
while(i * i < (n / 2)) {
int start = i * i;
int step = BFS(start,n);
if(step < ret)
ret = step;
i++;
}
return ret;
}
public int BFS(int start, int n) {
int step = 0;
LinkedList<Integer> queue = new LinkedList<Integer>();
queue.offer(start);
while(!queue.isEmpty()){
int node = queue.poll();
step++;
if(node == n)
break;
for(int k=1;k*k <= n;k++){
if(k*k <= n)
queue.offer(k * k + node);
if(node + k*k == n)
return step + 1;
}
}
return step;
}
}
У меня проблемы с обновлением значения шага.Я не могу придумать решение, как обновить значение шага.Кто-нибудь может помочь?