总和等于给定数n的最小平方数
任何数字都可以由一些完美的平方数之和表示。在这个问题中，我们需要发现代表给定值需要多少个最小平方的完美平方项。
令值为94，因此95=92+32+22+12。所以答案将是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