Perfect Squares

  • medium
  • tag: bfs, graph, math, DP, static var
  • similar: unique BST, word ladder, Flip Game
  • 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.

思路

  • 一开始我的思路很简单, 就是用小于n的所有平方数(从大到小, greedy?)来尝试, 类似Backtracking, 从而得到所有可能的组合, 然后返回list里面最短的组合. 其实就是DFS with prune.
  • 由于搜索很多可能性, 自然就很容易导致重复计算, 例如12-4=8, 然后计算8的组合情况. 但是之前已经计算过8的组合情况, 所以自然的想到了DP. state的定义: dp[i]就是数字i的最少组合解. 那么递推式是什么呢?
    • 很简单, 只考虑Math.min(dp[i-j*j]+1). 因为是perfect squares, 所以只和上一个数相差一个square. 当然有很多可能性, 所以找最小的那个

idea 1: dfs

  • 我的思路, 但实际上实现的时候很多要注意.
  • 参考代码如下:
public int numSquaresDFS(int n) {
    if (n == 0)  return 0;
    return dfs(n, 1, Integer.MAX_VALUE);
  }

// cost: 当前解, ans: 最终解.
private int dfs(int n, int cost, int ans) {
    if (cost >= ans)  return ans;
    int sq = (int) Math.sqrt(n);
    if (sq * sq == n)  return 1;
    for (int i = sq; i > 0; i--) {
      int tmp = 1 + dfs(n-i*i, cost+1, ans);
      if (tmp < ans)  ans = tmp;
    }
    return ans;
}

idea 2: 常见DP, 以及Stefan大牛的static DP

  • 先写一下常见的DP, 代码如下:
public int numSquaresDP(int n) {
    if (n <= 0)  return 0;
    int[] cntPerfectSquares = new int[n+1];
    cntPerfectSquares[0] = 0;
    for (int i = 1; i <= n; ++i) {
      cntPerfectSquares[i] = Integer.MAX_VALUE;
      for (int j = 1; j*j <= i; ++j) {
        cntPerfectSquares[i] = Math.min(cntPerfectSquares[i], cntPerfectSquares[i-j*j] + 1);
      }
    }
    return cntPerfectSquares[n];
}
  • 但是可以看到leetcode用了600个test case, 很有可能先找dp[100], 然后又找dp[50], 这时候怎样才能使得每次function call不重复计算呢?
    • ans: static dp list (因为不知道每次求得数是什么, 所以用动态数据结构.
  • 代码如下:
public int numSquaresStaticDP(int n) {
    if (n <= 0)  return 0;
    if (StcntPerfectSquares.size() == 0)  StcntPerfectSquares.add(0);
    while (StcntPerfectSquares.size() <= n) {
      int sz = StcntPerfectSquares.size();
      int cntSquares = Integer.MAX_VALUE;
      for (int i = 1; i * i <= sz; ++i) {
        cntSquares = Math.min(cntSquares, StcntPerfectSquares.get(sz-i*i) + 1);
      }
      StcntPerfectSquares.add(cntSquares);
    }
    return StcntPerfectSquares.get(n);
}

idea 3: BFS来做.

  • nice, 很漂亮的算法思想, 将题目转化为graph shortest path的问题, 直接用BFS.
  • 先知道, 题目要求时perfect squares, 所以任意2个相连的nodes都是相差平方数, 因为最大的n, 所以先求出所有小于等于n的平方数. 然后将所有平方数放到search queue里面, 看哪一个可以最短路径的到达n. 自然是想到BFS, 因为对于每一层来说, 都是按层递增距离的.
  • 同时注意每一个起点, 即平方数的时候, 都要初始化长度为1.
  • 这里有个关键, 当cur+j < n的时候, 若cur+j这个node已经走过, 那么第二次经过的话, 距离肯定只会增大. 因为是BFS的!
  • 这里更新的我对BFS的理解, 即对于每一个node起点, BFS都是保证了同一个while的时候, 每一个node所触及的当前点都是同样距离的.
  • 代码如下:
public int numSquareBFS(int n) {
    if (n <= 0)  return 0;
    int[] cntPerfectSquares = new int[n];
    List<Integer> perfectSquares = new ArrayList<>();
    for (int i = 1; i*i <= n; ++i) {
        perfectSquares.add(i*i);
        cntPerfectSquares[i*i-1] = 1;
    }
    if (cntPerfectSquares[n-1] == 1)  return 1;
    Queue<Integer> q = new LinkedList<>();
    for (int ps : perfectSquares) {
        q.offer(ps);
    }
    int curCnt = 1;
    while (!q.isEmpty()) {
        int sz = q.size();
        curCnt++;
        for (int i = 0; i < sz; ++i) {
            int tmp = q.poll();
            for (int j : perfectSquares) {
                if (tmp+j == n)  return curCnt;
                else if ((tmp+j < n) && (cntPerfectSquares[tmp+j-1] == 0)) {
                    cntPerfectSquares[tmp+j-1] = curCnt;
                    q.offer(tmp+j);
                }
                else if (tmp + j > n)  break;
            }
        } 
    }
    return 0;
}

idea *: 其实这是一个数学题

int is_square(int n){  
    int temp = (int) sqrt(n);  
    return temp * temp == n;  
}  

int numSquares(int n) {  
    while ((n & 3) == 0) //n%4 == 0  
        n >>= 2;  
    if ((n & 7) == 7) return 4; //n % 8 == 7  
    if(is_square(n)) return 1;  
    int sqrt_n = (int) sqrt(n);  
    for(int i = 1; i<= sqrt_n; i++){  
        if (is_square(n-i*i)) return 2;  
    }  
    return 3;  
}