寻找最小的“分解”方号码

Question

的问题，我试图解决：

给定一个int n，返回此int的最小的“分解”到里面全是方形的数字。
我们在这里定义因式分解的方式不是通常的方式：k到m数字（​​）的因式分解将如此：m1 + m2 + m3 + ... = k。

例如：让n = 12。最佳解决方案是：[4,4,4]，因为4是2的平方和4 + 4 + 4 = 12。也有[9,1,1,1]，虽然它不是最小的，因为它是前者的4个数字而不是3个。

---

我试图解决这个问题：

我的想法是给定的，我们将执行以下算法，数字n：
首先，我们将找到最近的平方数来n（例如，如果n = 82我们将找到81.
然后我们将递归计算我们得到的数减去最接近它的平方
这里是一个流程示例：假设n = 12和我们的f我们计算f(3) UNION {9}然后f(12-4) UNION {4}然后f(12-2) UNION {2}。从每个我们得到一个方形组合列表，我们从这些列表中选出最小列表。我们将这些保存在HashMap中以避免重复（动态编程风格）。在Java中（不完全）

代码尝试：

public List<Integer> getShortestSquareList(int n){ 
    HashMap<Integer,List<Integer>> map = new HashMap<Integer,List<Integer>(); 
    map.put(1, 1); 
    List<Integer> squareList = getSquareList(n); 
    return internalGetShortestSquareList(n, map, squareList); 
} 

List<Integer> getSquareList(int n){ 
    List<Integer> result=new ArrayList<Integer>(); 
    int i = 1; 
    while(i*i <= n){ 
     result.add(i*i); 
     i++; 
    } 
    return result; 
} 

public int getClosestSquare(int n,List<Integer> squareList){ 
    // getting the closestSquareIndex 
} 

public List<Integer> internalGetShortestSquareList(int n, HashMap<Integer m, HashMap<Integer,List<Integer>> map, List<Integer> squareList){ 
    if (map.contains(n)) {return map.get(n);} 
    int closestSqureIndex=getClosestSquare(m,squareList); 
    List<Integer> minSquareList; 
    int minSize=Integer.MAX_INT; 

    for(int i=closestSqureIndex; i>-1; i--) { 
      int square = squareList.get(closestSqureIndex); 
      List<Integer> tempSquares= new ArrayList<Integer>(square); 
      tempSquares.addAll(f(n-square, map, squareList)); 

      if (tempSquares.size() < minSize) { 
       minSize = tempSize; 
       minSquareList = tempSquares; 
      } 

    } 
    map.put(n, minSquareList);  
    return map.get(n);    
} 

---

我的问题：

看来，我的解决办法是不是最佳的（IMO）。我认为我的解决方案的时间复杂度为O(n)*O(Sqrt(n))，因为最大递归深度为n，最大子女数量为Sqrt(n)。我的解决方案可能充满了错误 - 这一点对我来说并不重要。我会很感激任何指导，以找到一个更优化的解决方案（伪代码或其他）。

Answer 1

基于@ trincot的link，我会建议一个简单的O(n sqrt n)算法。我们的想法是：

1. 使用在方形小于或等于n穷举搜索，以找出是否n是正方形本身，或任何两个或三个正方形小于n的总和。这可以在sqrt(n)^3时间完成，即O(n sqrt n)。
2. 如果失败，则在四个正方形中找到n的“因式分解”。

要递归地发现一些m的4因式分解，有三种情况现在：

1. m是一个素数和m mod 4 = 1。根据math，我们知道n是两个正方形的乘积。简单的穷举搜索或者更“肮脏”的方法都应该给出一个简单的答案。
2. m是一个素数和m mod 4 = 3。这种情况仍然需要详细说明，但可以使用link中描述的数学来实现。
3. m是一个复合数字。这是递归的情况。首先将因子m分解为两个因子，即整数u和v以便u*v=m。出于性能原因，它们应该尽可能接近，但这是一个小细节。

之后，递归地找到u和v的4因子分解。

然后，使用the formula：

(a^2+b^2+c^2+d^2) (A^2+B^2+C^2+D^2) = (aA+bB+cC+dD)^2 + (aB-bA+cD-dC)^2 + (aC-bD-cA+dB)^2 + (aD-dA+bC-cB)^2 

找到m 4因式分解。这里我表示u = (a^2+b^2+c^2+d^2)和v = (A^2+B^2+C^2+D^2)，因为他们的4因子化在这一点上是已知的。