总和等于给定数n的最小平方数

任何数字都可以由一些完美的平方数之和表示。在这个问题中，我们需要发现代表给定值需要多少个最小平方的完美平方项。

令值为94，因此95 = 9 ² + 3 ² + 2 ² + 1 ²。所以答案将是4

这个想法是从1开始，我们进一步前进以获得完美的平方数。当值为1到3时，它们只能由1组成。

输入输出

Input:
An integer number. Say 63.
Output:
Number of squared terms. Here the answer is 4.
63 =72 + 32 + 22 + 1

算法

minSquareTerms(value)

输入：给定值。

输出：达到给定值的最小平方数。

Begin
   define array sqList of size value + 1
   sqList[0] := 0, sqList[1] := 1, sqList[2] := 2, sqList[3] := 3

   for i in range 4 to n, do
      sqList[i] := i
      for x := 1 to i, do
         temp := x^2
         if temp > i, then
            break the loop
         else sqList[i] := minimum of sqList[i] and (1+sqList[i-temp])
      done
   done
   return sqList[n]
End

示例

#include<bits/stdc++.h>
using namespace std;

int min(int x, int y) {
   return (x < y)? x: y;
}

int minSquareTerms(int n) {
   int *squareList = new int[n+1];

   //对于0到3，需要全部1 ^ 2来表示

   squareList[0] = 0;
   squareList[1] = 1;
   squareList[2] = 2;
   squareList[3] = 3;

   for (int i = 4; i <= n; i++) {
      squareList[i] = i; //initially store the maximum value as i

      for (int x = 1; x <= i; x++) {
         int temp = x*x;      //find a square term, lower than the number i
         if (temp > i)
            break;
         else squareList[i] = min(squareList[i], 1+squareList[itemp]);
      }
   }
   return squareList[n];
}

int main() {
   int n;
   cout << "Enter a number: "; cin >> n;
   cout << "Minimum Squared Term needed: " << minSquareTerms(n);
   return 0;
}

输出结果

Enter a number: 63
Minimum Squared Term needed: 4