【leetcode】BFS问题

Perfect Squares

题目

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

分析

典型的BFS题目

方法：

需要一个队列记录当前剩余的和。

首先将n加入队列，然后n出队列，计算小于他的最大平方数，然后递减计算剩余的数字差，如如队列，层数+1

当队列中有某一层出现剩余的和为0的时候说明找到了一条合法相加形式，此时就是所需的最少数组组合，返回此时的depth即可。

优化：DP

dp[n]：记录n可以由几个平方数加和得到

递推公式：dp[n] = min(dp[n-1]+1,dp[n-4]+1,dp[n-9]+1,……)

初始化：

​ dp[0] = 0;

​ dp[1] = 1;

返回值：dp[n]

代码

public int numSquares(int n) {
  Queue<Integer> queue = new LinkedList<>();
  queue.add(n);
  int depth = 0;
  while(!queue.isEmpty()){
    depth++;
    int size = queue.size();
    while (size > 0){
      int temp = queue.poll();
      //计算小于等于n的最大的平方数
      int maxSquare = (int) Math.sqrt(temp);
      while(maxSquare > 0){
        int sumLeft = temp - maxSquare*maxSquare;
        if(sumLeft == 0){//和等于0了
          return depth;
        }
        queue.add(sumLeft);
        maxSquare--;
      }
      size--;
    }
  }
  return 0;
}

//动态规划
public int numSquares(int n) {
  if(n == 0){
    return 0;
  }
  int[] dp = new int[n+1];
  dp[0] = 0;
  dp[1] = 1;
  for(int i = 2; i <= n;i++){
    int dpMinTemp = dp[i-1] +1;

    for(int j = 2;j*j <= i;j++){
      dpMinTemp = Math.min(dpMinTemp,dp[i - j*j] +1);
    }
    dp[i] = dpMinTemp;
  }
  return dp[n];
}