查找號碼的最短平方和

Question

查找並輸出給定​​號碼的最短平方和。

實施例：12 = 2^2 + 2^2 + 2^2 (not 3^2 + 1^2 + 1^2 + 1^2)

輸出：{2 2 2}

Answer 1

這是最小的硬幣變化的問題，其中所述硬幣是[1,4,9,...,(ceil(sqrt(n)))^2]。

它可以使用Dynamic Programming (DP)由下列遞推公式解決：

D(i,0) = 0 
D(i,x) = infinity x<0 
D(0,x) = infinity x>0 
D(i,x) = min { D(i,x-i^2) + 1, D(i-1,x) } 

當建立您的矩陣（假定自下而上DP），在D(ceil(sqrt(n)),n)在矩陣表示的元素爲「硬幣的最小數「（平方數）需要建立你的輸入號碼。

獲取實際元素是通過在構建矩陣後跟蹤您在矩陣中的選擇來完成的，並且在每個點檢查您是否添加了加法或不加。
對this thread和this thread中的類似問題進行了更詳細的解釋。

Answer 2

下面是該問題的可視化基本解決方案。 需要進行編輯以緩存中間答案，以便算法顯着更快。目前...只有大約40到50的值才能被快速計算出來。這是完全正常工作和測試。它只返回最短的答案，以及其中較高值在其他值左側的答案。

Private Function ShortestSquareSum(x As Integer) As Integer()() 
    If x < 0 Then 
     Throw New ArgumentException("Parameter cannot be negative.", "x") 
    ElseIf x = 0 Then 
     Return New Integer()() {New Integer() {}} 
    Else 
     Dim answers As New List(Of Integer()) 
     Dim shortest As Integer? = Nothing 
     For y As Integer = Math.Floor(Math.Sqrt(x)) To 1 Step -1 
      Dim remaining As Integer = x - y * y 
      Dim tempAnswers As Integer()() = ShortestSquareSum(x - y * y) 
      For Each answer As Integer() In tempAnswers 
       Dim currentAnswer As New List(Of Integer) 
       currentAnswer.Add(y) 
       currentAnswer.AddRange(answer) 
       If Not shortest.HasValue OrElse currentAnswer.Count < shortest Then 
        shortest = currentAnswer.Count 
        answers.Clear() 
        answers.Add(currentAnswer.ToArray()) 
       ElseIf currentAnswer.Count = shortest AndAlso (answer.Count = 0 OrElse y > answer(0)) Then 
        answers.Add(currentAnswer.ToArray()) 
       End If 
      Next 
     Next 
     Return answers.ToArray() 
    End If 
End Function 

Answer 3

public static void shortest_square(int n) 
{ 
    int i=2; 
    List<Integer> list= new ArrayList<Integer>(); 
    while(i<=n) || n!=0) 
    { 
    if(n%(i*i)==0) 
    { 
     n=n-(i*i); 
     list.add(i); 
    } 
    else 
    { 
     i++; 
    } 

    } 
    System.out.println(list); 
}