279. Perfect Squares
アプローチ 1
DP
package com.leetcode.midium;
import java.util.Arrays;
public class PerfectSquares279 {
public static void main(String[] args) {
}
public static int numSquares(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j * j <= i; j++) {
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
}
}
return dp[n];
}
}
アプローチ 2
BFS
class Solution {
public int numSquares(int n) {
Queue<Integer> queue = new LinkedList<Integer>();
Set<Integer> alreadyAddedSquareNumbers = new HashSet<Integer>();
int level = 0;
queue.add(0);
while(!queue.isEmpty()){
level++;
int previousLevel = queue.size();
for(int index = 0; index < previousLevel; index++){
int base = queue.poll();
for(int square = 1; square * square <= n - base; square++){
int sumOfSquares = base + square * square;
if(alreadyAddedSquareNumbers.contains(base + square * square) || sumOfSquares > n){
continue;
}
if(sumOfSquares == n) {
return level;
} else {
queue.add(sumOfSquares);
alreadyAddedSquareNumbers.add(sumOfSquares);
}
}
}
}
return -1;
}
}