一个数字总是可以表示为其他数字的平方和。请注意，1是一个正方形，我们总是可以将一个数字分解为（1*1+1*1+1*1+…）。给定一个数n，求出和X之和的最小平方数。
null
例如：
输入： n=100 输出： 1. 说明： 100可以写成10 2. .请注意，100也可以写成5 2. + 5 2. + 5 2. + 5 2. ，但这种表示法需要4个正方形。
输入： n=6 输出 : 3
这个想法很简单，我们从1开始，到一个平方小于或等于n的数。对于每个数x，我们重复n-x。下面是递归公式。
If n = 1 and x*x <= n
下面是基于上述递归公式的简单递归解决方案。
C++
// A naive recursive C++ // program to find minimum // number of squares whose sum // is equal to a given number #include <bits/stdc++.h> using namespace std; // Returns count of minimum // squares that sum to n int getMinSquares(unsigned int n) { // base cases // if n is perfect square then // Minimum squares required is 1 // (144 = 12^2) if ( sqrt (n) - floor ( sqrt (n)) == 0) return 1; if (n <= 3) return n; // getMinSquares rest of the // table using recursive // formula // Maximum squares required // is n (1*1 + 1*1 + ..) int res = n; // Go through all smaller numbers // to recursively find minimum for ( int x = 1; x <= n; x++) { int temp = x * x; if (temp > n) break ; else res = min(res, 1 + getMinSquares (n - temp)); } return res; } // Driver code int main() { cout << getMinSquares(6); return 0; } |
JAVA
// A naive recursive JAVA // program to find minimum // number of squares whose // sum is equal to a given number class squares { // Returns count of minimum // squares that sum to n static int getMinSquares( int n) { // base cases if (n <= 3 ) return n; // getMinSquares rest of the // table using recursive // formula // Maximum squares required is int res = n; // n (1*1 + 1*1 + ..) // Go through all smaller numbers // to recursively find minimum for ( int x = 1 ; x <= n; x++) { int temp = x * x; if (temp > n) break ; else res = Math.min(res, 1 + getMinSquares(n - temp)); } return res; } // Driver code public static void main(String args[]) { System.out.println(getMinSquares( 6 )); } } /* This code is contributed by Rajat Mishra */ |
Python3
# A naive recursive Python program to # find minimum number of squares whose # sum is equal to a given number # Returns count of minimum squares # that sum to n def getMinSquares(n): # base cases if n < = 3 : return n; # getMinSquares rest of the table # using recursive formula # Maximum squares required # is n (1 * 1 + 1 * 1 + ..) res = n # Go through all smaller numbers # to recursively find minimum for x in range ( 1 , n + 1 ): temp = x * x; if temp > n: break else : res = min (res, 1 + getMinSquares(n - temp)) return res; # Driver code print (getMinSquares( 6 )) # This code is contributed by nuclode |
C#
// A naive recursive C# program // to find minimum number of // squares whose sum is equal // to a given number using System; class GFG { // Returns count of minimum // squares that sum to n static int getMinSquares( int n) { // base cases if (n <= 3) return n; // getMinSquares rest of the // table using recursive // formula // Maximum squares required is // n (1*1 + 1*1 + ..) int res = n; // Go through all smaller numbers // to recursively find minimum for ( int x = 1; x <= n; x++) { int temp = x * x; if (temp > n) break ; else res = Math.Min(res, 1 + getMinSquares(n - temp)); } return res; } // Driver Code public static void Main() { Console.Write(getMinSquares(6)); } } // This code is contributed by nitin mittal |
PHP
<?php // A naive recursive PHP program // to find minimum number of // squares whose sum is equal // to a given number // Returns count of minimum // squares that sum to n function getMinSquares( $n ) { // base cases if ( $n <= 3) return $n ; // getMinSquares rest of the // table using recursive formula // Maximum squares required // is n (1*1 + 1*1 + ..) $res = $n ; // Go through all smaller numbers // to recursively find minimum for ( $x = 1; $x <= $n ; $x ++) { $temp = $x * $x ; if ( $temp > $n ) break ; else $res = min( $res , 1 + getMinSquares( $n - $temp )); } return $res ; } // Driver Code echo getMinSquares(6); // This code is contributed // by nitin mittal. ?> |
Javascript
<script> // A naive recursive Javascript program // to find minimum number of squares // whose sum is equal to a given number // Returns count of minimum // squares that sum to n function getMinSquares(n) { // base cases if (n <= 3) return n; // getMinSquares rest of the // table using recursive // formula // Maximum squares required is // n (1*1 + 1*1 + ..) let res = n; // Go through all smaller numbers // to recursively find minimum for (let x = 1; x <= n; x++) { let temp = x * x; if (temp > n) break ; else res = Math.min(res, 1 + getMinSquares(n - temp)); } return res; } // Driver code document.write(getMinSquares(6)); // This code is contributed by suresh07 </script> |
输出
3
上述解的时间复杂度是指数的。如果我们画递归树，我们可以观察到许多子问题被一次又一次地解决。例如，当我们从n=6开始，我们可以通过减去1 2次，再减去2 1次，得到4。所以4的子问题被调用了两次。
由于再次调用相同的子问题，此问题具有重叠子问题属性。所以最小平方和问题有两个性质（参见 这 和 这 )一个动态规划问题。像其他典型的 动态规划问题 ，可以通过以自下而上的方式构造临时数组表[]，避免重新计算相同的子问题。下面是一个基于动态规划的解决方案。
C++
// A dynamic programming based // C++ program to find minimum // number of squares whose sum // is equal to a given number #include <bits/stdc++.h> using namespace std; // Returns count of minimum // squares that sum to n int getMinSquares( int n) { // We need to check base case // for n i.e. 0,1,2 // the below array creation // will go OutOfBounds. if (n<=3) return n; // Create a dynamic // programming table // to store sq int * dp = new int [n + 1]; // getMinSquares table // for base case entries dp[0] = 0; dp[1] = 1; dp[2] = 2; dp[3] = 3; // getMinSquares rest of the // table using recursive // formula for ( int i = 4; i <= n; i++) { // max value is i as i can // always be represented // as 1*1 + 1*1 + ... dp[i] = i; // Go through all smaller numbers to // to recursively find minimum for ( int x = 1; x <= ceil ( sqrt (i)); x++) { int temp = x * x; if (temp > i) break ; else dp[i] = min(dp[i], 1 + dp[i - temp]); } } // Store result and free dp[] int res = dp[n]; delete [] dp; return res; } // Driver code int main() { cout << getMinSquares(6); return 0; } |
JAVA
// A dynamic programming based // JAVA program to find minimum // number of squares whose sum // is equal to a given number class squares { // Returns count of minimum // squares that sum to n static int getMinSquares( int n) { // We need to add a check // here for n. If user enters // 0 or 1 or 2 // the below array creation // will go OutOfBounds. if (n <= 3 ) return n; // Create a dynamic programming // table // to store sq int dp[] = new int [n + 1 ]; // getMinSquares table for // base case entries dp[ 0 ] = 0 ; dp[ 1 ] = 1 ; dp[ 2 ] = 2 ; dp[ 3 ] = 3 ; // getMinSquares rest of the // table using recursive // formula for ( int i = 4 ; i <= n; i++) { // max value is i as i can // always be represented // as 1*1 + 1*1 + ... dp[i] = i; // Go through all smaller numbers to // to recursively find minimum for ( int x = 1 ; x <= Math.ceil( Math.sqrt(i)); x++) { int temp = x * x; if (temp > i) break ; else dp[i] = Math.min(dp[i], 1 + dp[i - temp]); } } // Store result and free dp[] int res = dp[n]; return res; } // Driver Code public static void main(String args[]) { System.out.println(getMinSquares( 6 )); } } /* This code is contributed by Rajat Mishra */ |
Python3
# A dynamic programming based Python # program to find minimum number of # squares whose sum is equal to a # given number from math import ceil, sqrt # Returns count of minimum squares # that sum to n def getMinSquares(n): # Create a dynamic programming table # to store sq and getMinSquares table # for base case entries dp = [ 0 , 1 , 2 , 3 ] # getMinSquares rest of the table # using recursive formula for i in range ( 4 , n + 1 ): # max value is i as i can always # be represented as 1 * 1 + 1 * 1 + ... dp.append(i) # Go through all smaller numbers # to recursively find minimum for x in range ( 1 , int (ceil(sqrt(i))) + 1 ): temp = x * x; if temp > i: break else : dp[i] = min (dp[i], 1 + dp[i - temp]) # Store result return dp[n] # Driver code print (getMinSquares( 6 )) # This code is contributed by nuclode |
C#
// A dynamic programming based // C# program to find minimum // number of squares whose sum // is equal to a given number using System; class squares { // Returns count of minimum // squares that sum to n static int getMinSquares( int n) { // We need to add a check here // for n. If user enters 0 or 1 or 2 // the below array creation will go // OutOfBounds. if (n <= 3) return n; // Create a dynamic programming // table to store sq int [] dp = new int [n + 1]; // getMinSquares table for base // case entries dp[0] = 0; dp[1] = 1; dp[2] = 2; dp[3] = 3; // getMinSquares for rest of the // table using recursive formula for ( int i = 4; i <= n; i++) { // max value is i as i can // always be represented // as 1 * 1 + 1 * 1 + ... dp[i] = i; // Go through all smaller numbers to // to recursively find minimum for ( int x = 1; x <= Math.Ceiling( Math.Sqrt(i)); x++) { int temp = x * x; if (temp > i) break ; else dp[i] = Math.Min(dp[i], 1 + dp[i - temp]); } } // Store result and free dp[] int res = dp[n]; return res; } // Driver Code public static void Main(String[] args) { Console.Write(getMinSquares(6)); } } // This code is contributed by Nitin Mittal. |
PHP
<?php // A dynamic programming based // PHP program to find minimum // number of squares whose sum // is equal to a given number // Returns count of minimum // squares that sum to n function getMinSquares( $n ) { // Create a dynamic programming // table to store sq $dp ; // getMinSquares table for // base case entries $dp [0] = 0; $dp [1] = 1; $dp [2] = 2; $dp [3] = 3; // getMinSquares rest of the // table using recursive formula for ( $i = 4; $i <= $n ; $i ++) { // max value is i as i can // always be represented // as 1*1 + 1*1 + ... $dp [ $i ] = $i ; // Go through all smaller // numbers to recursively // find minimum for ( $x = 1; $x <= ceil (sqrt( $i )); $x ++) { $temp = $x * $x ; if ( $temp > $i ) break ; else $dp [ $i ] = min( $dp [ $i ], (1 + $dp [ $i - $temp ])); } } // Store result // and free dp[] $res = $dp [ $n ]; // delete $dp; return $res ; } // Driver Code echo getMinSquares(6); // This code is contributed // by shiv_bhakt. ?> |
Javascript
<script> // A dynamic programming based // javascript program to find minimum // number of squares whose sum // is equal to a given number // Returns count of minimum // squares that sum to n function getMinSquares( n) { // We need to add a check here // for n. If user enters 0 or 1 or 2 // the below array creation will go // OutOfBounds. if (n <= 3) return n; // Create a dynamic programming // table to store sq var dp = new Array(n + 1); // getMinSquares table for base // case entries dp[0] = 0; dp[1] = 1; dp[2] = 2; dp[3] = 3; // getMinSquares for rest of the // table using recursive formula for ( var i = 4; i <= n; i++) { // max value is i as i can // always be represented // as 1 * 1 + 1 * 1 + ... dp[i] = i; // Go through all smaller numbers to // to recursively find minimum for ( var x = 1; x <= Math.ceil( Math.sqrt(i)); x++) { var temp = x * x; if (temp > i) break ; else dp[i] = Math.min(dp[i], 1 + dp[i - temp]); } } // Store result and free dp[] var res = dp[n]; return res; } // Driver Code document.write(getMinSquares(6)); </script> |
输出
3
感谢Gaurav Ahirwar提出这个解决方案。
另一种方法：（使用备忘录）
这个问题也可以用记忆法（动态规划）来解决。
以下是实施情况：
C++
#include <bits/stdc++.h> using namespace std; int minCount( int n) { int * minSquaresRequired = new int [n + 1]; minSquaresRequired[0] = 0; minSquaresRequired[1] = 1; for ( int i = 2; i <= n; ++i) { minSquaresRequired[i] = INT_MAX; for ( int j = 1; i - (j * j) >= 0; ++j) { minSquaresRequired[i] = min(minSquaresRequired[i], minSquaresRequired[i - (j * j)]); } minSquaresRequired[i] += 1; } int result = minSquaresRequired[n]; delete [] minSquaresRequired; return result; } // Driver code int main() { cout << minCount(6); return 0; } |
JAVA
import java.util.*; class GFG { static int minCount( int n) { int [] minSquaresRequired = new int [n + 1 ]; minSquaresRequired[ 0 ] = 0 ; minSquaresRequired[ 1 ] = 1 ; for ( int i = 2 ; i <= n; ++i) { minSquaresRequired[i] = Integer.MAX_VALUE; for ( int j = 1 ; i - (j * j) >= 0 ; ++j) { minSquaresRequired[i] = Math.min(minSquaresRequired[i], minSquaresRequired[i - (j * j)]); } minSquaresRequired[i] += 1 ; } int result = minSquaresRequired[n]; return result; } // Driver code public static void main(String[] args) { System.out.print(minCount( 6 )); } } // This code contributed by gauravrajput1 |
Python3
import sys def minCount(n): minSquaresRequired = [ 0 for i in range (n + 1 )]; minSquaresRequired[ 0 ] = 0 ; minSquaresRequired[ 1 ] = 1 ; for i in range ( 2 ,n + 1 ): minSquaresRequired[i] = sys.maxsize; j = 1 for j in range ( 1 ,i - (j * j)): if (i - (j * j) > = 0 ): minSquaresRequired[i] = min (minSquaresRequired[i], minSquaresRequired[i - (j * j)]); else : break minSquaresRequired[i] + = 1 ; result = minSquaresRequired[n]; return result; # Driver code if __name__ = = '__main__' : print (minCount( 6 )); # This code is contributed by umadevi9616 |
C#
using System; class GFG { static int minCount( int n) { int [] minSquaresRequired = new int [n + 1]; minSquaresRequired[0] = 0; minSquaresRequired[1] = 1; for ( int i = 2; i <= n; ++i) { minSquaresRequired[i] = Int32.MaxValue; for ( int j = 1; i - (j * j) >= 0; ++j) { minSquaresRequired[i] = Math.Min(minSquaresRequired[i], minSquaresRequired[i - (j * j)]); } minSquaresRequired[i] += 1; } int result = minSquaresRequired[n]; return result; } // Driver code public static void Main(String[] args) { Console.Write(minCount(6)); } } // This code is contributed by shivanisinghss2110 |
Javascript
<script> // JavaScript Program to implement // the above approach function minCount(n) { let minSquaresRequired = new Array(n + 1); minSquaresRequired[0] = 0; minSquaresRequired[1] = 1; for (let i = 2; i <= n; ++i) { minSquaresRequired[i] = Number.MAX_VALUE; for (let j = 1; i - (j * j) >= 0; ++j) { minSquaresRequired[i] = Math.min(minSquaresRequired[i], minSquaresRequired[i - (j * j)]); } minSquaresRequired[i] += 1; } let result = minSquaresRequired[n]; return result; } // Driver code document.write(minCount(6)); // This code is contributed by Potta Lokesh </script> |
输出
3
另一种方法： 这个问题也可以通过使用图表来解决。以下是如何做到这一点的基本思路。 我们将使用BFS（广度优先搜索）来寻找从给定值n到0的最小步数。 因此，对于每个节点，我们将下一个可能的有效路径推送到一个队列中， 如果它到达节点0，我们将更新我们的答案，如果它小于答案。
以下是上述方法的实施情况：
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count minimum // squares that sum to n int numSquares( int n) { // Creating visited vector // of size n + 1 vector< int > visited(n + 1,0); // Queue of pair to store node // and number of steps queue< pair< int , int > >q; // Initially ans variable is // initialized with inf int ans = INT_MAX; // Push starting node with 0 // 0 indicate current number // of step to reach n q.push({n,0}); // Mark starting node visited visited[n] = 1; while (!q.empty()) { pair< int , int > p; p = q.front(); q.pop(); // If node reaches its destination // 0 update it with answer if (p.first == 0) ans=min(ans, p.second); // Loop for all possible path from // 1 to i*i <= current node(p.first) for ( int i = 1; i * i <= p.first; i++) { // If we are standing at some node // then next node it can jump to will // be current node- // (some square less than or equal n) int path=(p.first - (i*i)); // Check if it is valid and // not visited yet if (path >= 0 && ( !visited[path] || path == 0)) { // Mark visited visited[path]=1; // Push it it Queue q.push({path,p.second + 1}); } } } // Return ans to calling function return ans; } // Driver code int main() { cout << numSquares(12); return 0; } |
JAVA
// Java program for the above approach import java.util.*; import java.awt.Point; class GFG { // Function to count minimum // squares that sum to n public static int numSquares( int n) { // Creating visited vector // of size n + 1 int visited[] = new int [n + 1 ]; // Queue of pair to store node // and number of steps Queue<Point> q = new LinkedList<>(); // Initially ans variable is // initialized with inf int ans = Integer.MAX_VALUE; // Push starting node with 0 // 0 indicate current number // of step to reach n q.add( new Point(n, 0 )); // Mark starting node visited visited[n] = 1 ; while (q.size() != 0 ) { Point p = q.peek(); q.poll(); // If node reaches its destination // 0 update it with answer if (p.x == 0 ) ans = Math.min(ans, p.y); // Loop for all possible path from // 1 to i*i <= current node(p.first) for ( int i = 1 ; i * i <= p.x; i++) { // If we are standing at some node // then next node it can jump to will // be current node- // (some square less than or equal n) int path = (p.x - (i * i)); // Check if it is valid and // not visited yet if (path >= 0 && (visited[path] == 0 || path == 0 )) { // Mark visited visited[path] = 1 ; // Push it it Queue q.add( new Point(path, p.y + 1 )); } } } // Return ans to calling function return ans; } // Driver code public static void main(String[] args) { System.out.println(numSquares( 12 )); } } // This code is contributed by divyesh072019 |
Python3
# Python3 program for the above approach import sys # Function to count minimum # squares that sum to n def numSquares(n) : # Creating visited vector # of size n + 1 visited = [ 0 ] * (n + 1 ) # Queue of pair to store node # and number of steps q = [] # Initially ans variable is # initialized with inf ans = sys.maxsize # Push starting node with 0 # 0 indicate current number # of step to reach n q.append([n, 0 ]) # Mark starting node visited visited[n] = 1 while ( len (q) > 0 ) : p = q[ 0 ] q.pop( 0 ) # If node reaches its destination # 0 update it with answer if (p[ 0 ] = = 0 ) : ans = min (ans, p[ 1 ]) # Loop for all possible path from # 1 to i*i <= current node(p.first) i = 1 while i * i < = p[ 0 ] : # If we are standing at some node # then next node it can jump to will # be current node- # (some square less than or equal n) path = p[ 0 ] - i * i # Check if it is valid and # not visited yet if path > = 0 and (visited[path] = = 0 or path = = 0 ) : # Mark visited visited[path] = 1 # Push it it Queue q.append([path,p[ 1 ] + 1 ]) i + = 1 # Return ans to calling function return ans print (numSquares( 12 )) # This code is contributed by divyeshrabadiya07 |
C#
// C# program for the above approach using System; using System.Collections; using System.Collections.Generic; class GFG{ public class Point { public int x, y; public Point( int x, int y) { this .x = x; this .y = y; } } // Function to count minimum // squares that sum to n public static int numSquares( int n) { // Creating visited vector // of size n + 1 int []visited = new int [n + 1]; // Queue of pair to store node // and number of steps Queue q = new Queue(); // Initially ans variable is // initialized with inf int ans = 1000000000; // Push starting node with 0 // 0 indicate current number // of step to reach n q.Enqueue( new Point(n, 0)); // Mark starting node visited visited[n] = 1; while (q.Count != 0) { Point p = (Point)q.Dequeue(); // If node reaches its destination // 0 update it with answer if (p.x == 0) ans = Math.Min(ans, p.y); // Loop for all possible path from // 1 to i*i <= current node(p.first) for ( int i = 1; i * i <= p.x; i++) { // If we are standing at some node // then next node it can jump to will // be current node- // (some square less than or equal n) int path = (p.x - (i * i)); // Check if it is valid and // not visited yet if (path >= 0 && (visited[path] == 0 || path == 0)) { // Mark visited visited[path] = 1; // Push it it Queue q.Enqueue( new Point(path, p.y + 1)); } } } // Return ans to calling function return ans; } // Driver code public static void Main( string [] args) { Console.Write(numSquares(12)); } } // This code is contributed by rutvik_56 |
输出
3
上述问题的时间复杂度为O（n）*sqrt（n），优于递归方法。 此外，这也是了解BFS（广度优先搜索）工作原理的好方法。
如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写一封电子邮件。
另一种方法：
这个问题也可以用动态规划（自下而上的方法）来解决。这个想法就像硬币兑换2（在其中，我们需要告诉最小数量的硬币，从给定的硬币[]数组中生成一个数量），在这里，所有小于或等于n的完美正方形的数组可以被硬币[]数组替换，数量可以被n替换。只需将其视为一个无界背包问题，让我们来看一个例子：
对于给定的输入n=6，我们将创建一个高达4的数组，arr:[1,4]
这里的答案是（4+1+1=6），即3。
以下是上述方法的实施情况：
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count minimum // squares that sum to n int numSquares( int n) { //Making the array of perfect squares less than or equal to n vector < int > arr; int i = 1; while (i*i <= n){ arr.push_back(i*i); i++; } //A dp array which will store minimum number of perfect squares //required to make n from i at i th index vector < int > dp(n+1, INT_MAX); dp[n] = 0; for ( int i = n-1; i>=0; i--){ //checking from i th value to n value minimum perfect squares required for ( int j = 0; j<arr.size(); j++){ //check if index doesn't goes out of bound if (i + arr[j] <= n){ dp[i] = min(dp[i], dp[i+arr[j]]); } } //from current to go to min step one i we need to take one step dp[i]++; } return dp[0]; } // Driver code int main() { cout << numSquares(12); return 0; } |
JAVA
// Java program for the above approach import java.util.*; class GFG { // Function to count minimum // squares that sum to n static int numSquares( int n) { // Making the array of perfect squares less than or equal to n Vector <Integer> arr = new Vector<>(); int k = 1 ; while (k * k <= n){ arr.add(k * k); k++; } // A dp array which will store minimum number of perfect squares // required to make n from i at i th index int []dp = new int [n + 1 ]; Arrays.fill(dp, Integer.MAX_VALUE); dp[n] = 0 ; for ( int i = n - 1 ; i >= 0 ; i--) { // checking from i th value to n value minimum perfect squares required for ( int j = 0 ; j < arr.size(); j++) { // check if index doesn't goes out of bound if (i + arr.elementAt(j) <= n) { dp[i] = Math.min(dp[i], dp[i+arr.elementAt(j)]); } } // from current to go to min step one i we need to take one step dp[i]++; } return dp[ 0 ]; } // Driver code public static void main(String[] args) { System.out.print(numSquares( 12 )); } } // This code is contributed by umadevi9616. |
Python3
# Python program for the above approach import sys # Function to count minimum # squares that sum to n def numSquares(n): # Making the array of perfect squares less than or equal to n arr = []; k = 1 ; while (k * k < = n): arr.append(k * k); k + = 1 ; # A dp array which will store minimum number of perfect squares # required to make n from i at i th index dp = [sys.maxsize for i in range (n + 1 )]; dp[n] = 0 ; for i in range (n - 1 , - 1 , - 1 ): # checking from i th value to n value minimum perfect squares required for j in range ( len (arr)): # check if index doesn't goes out of bound if (i + arr[j] < = n): dp[i] = min (dp[i], dp[i + arr[j]]); # from current to go to min step one i we need to take one step dp[i] + = 1 ; return dp[ 0 ]; # Driver code if __name__ = = '__main__' : print (numSquares( 12 )); # This code is contributed by gauravrajput1 |
C#
// C# program for the above approach using System; using System.Collections.Generic; public class GFG { // Function to count minimum // squares that sum to n static int numSquares( int n) { // Making the array of perfect squares less than or equal to n List < int > arr = new List< int >(); int k = 1; while (k * k <= n){ arr.Add(k * k); k++; } // A dp array which will store minimum number of perfect squares // required to make n from i at i th index int []dp = new int [n + 1]; for ( int i = 0; i < n + 1; i++) dp[i] = int .MaxValue; dp[n] = 0; for ( int i = n - 1; i >= 0; i--) { // checking from i th value to n value minimum perfect squares required for ( int j = 0; j < arr.Count; j++) { // check if index doesn't goes out of bound if (i + arr[j] <= n) { dp[i] = Math.Min(dp[i], dp[i+arr[j]]); } } // from current to go to min step one i we need to take one step dp[i]++; } return dp[0]; } // Driver code public static void Main(String[] args) { Console.Write(numSquares(12)); } } // This code is contributed by umadevi9616 |
Javascript
<script> // javascript program for the above approach // Function to count minimum // squares that sum to n function numSquares(n) { // Making the array of perfect squares less than or equal to n var arr = new Array(); var k = 1; while (k * k <= n) { arr.push(k * k); k++; } // A dp array which will store minimum number of perfect squares // required to make n from i at i th index var dp = Array(n + 1).fill(Number.MAX_VALUE); dp[n] = 0; for (i = n - 1; i >= 0; i--) { // checking from i th value to n value minimum perfect squares required for (j = 0; j < arr.length; j++) { // check if index doesn't goes out of bound if (i + arr[j] <= n) { dp[i] = Math.min(dp[i], dp[i + arr[j]]); } } // from current to go to min step one i we need to take one step dp[i]++; } return dp[0]; } // Driver code document.write(numSquares(12)); // This code is contributed by umadevi9616 </script> |
输出
3
上述问题的时间复杂度为O（n）*sqrt（n），因为数组将在sqrt（n）时间内生成，而填充dp数组的for循环将花费n*sqrt（n）时间。dp阵列的大小为n，因此这种方法的空间复杂度为O（n）。
另一种方法：（使用数学）
该解决方案基于拉格朗日的四平方定理。 根据这个定理，这个问题可以有4个解，即1，2，3，4
案例1：
Ans=1=>如果数字是平方数，则可能发生这种情况。 n={a 2. ：a∈ W} 示例：1、4、9等。
案例2：
Ans=2=>如果数字是两个平方数的和，则这是可能的。
n={a 2. +b 2. ：a，b∈ W} 示例：2、5、18等。
案例3：
Ans=3=>如果数字不是形式4，则可能发生这种情况 K （8m+7）。
有关这方面的更多信息： https://en.wikipedia.org/wiki/Legendre%27s_three-平方定理
n={a 2. +b 2. +c 2. ：a、b、c∈ W}⟷ n≢ {4k（8m+7）：k，m∈ W} 例：6、11、12等。
案例4：
Ans=4=>如果数字的形式为4，则可能发生这种情况 K （8m+7）。
n={a 2. +b 2. +c 2. +d 2. ：a、b、c、d∈ W}⟷ n≡ {4k（8m+7）：k，m∈ W} 例：7、15、23等。
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; // returns true if the input number x is a square number, // else returns false bool isSquare( int x) { int sqRoot = sqrt (x); return (sqRoot * sqRoot == x); } // Function to count minimum squares that sum to n int cntSquares( int n) { // ans = 1 if the number is a perfect square if (isSquare(n)) { return 1; } // ans = 2: // we check for each i if n - (i * i) is a perfect // square for ( int i = 1; i <= ( int ) sqrt (n); i++) { if (isSquare(n - (i * i))) { return 2; } } // ans = 4 // possible if the number is representable in the form // 4^a (8*b + 7). while (n % 4 == 0) { n >>= 2; } if (n % 8 == 7) { return 4; } // since all the other cases have been evaluated, the // answer can only then be 3 if the program reaches here return 3; } // Driver Code int main() { cout << cntSquares(12) << endl; return 0; } |
JAVA
// Java code for the above approach import java.util.*; class GFG{ // returns true if the input number x is a square number, // else returns false static boolean isSquare( int x) { int sqRoot = ( int )Math.sqrt(x); return (sqRoot * sqRoot == x); } // Function to count minimum squares that sum to n static int cntSquares( int n) { // ans = 1 if the number is a perfect square if (isSquare(n)) { return 1 ; } // ans = 2: // we check for each i if n - (i * i) is a perfect // square for ( int i = 1 ; i <= ( int )Math.sqrt(n); i++) { if (isSquare(n - (i * i))) { return 2 ; } } // ans = 4 // possible if the number is representable in the form // 4^a (8*b + 7). while (n % 4 == 0 ) { n >>= 2 ; } if (n % 8 == 7 ) { return 4 ; } // since all the other cases have been evaluated, the // answer can only then be 3 if the program reaches here return 3 ; } // Driver Code public static void main(String[] args) { System.out.print(cntSquares( 12 ) + "" ); } } // This code is contributed by umadevi9616 |
Python3
# Python code for the above approach import math # returns True if the input number x is a square number, # else returns False def isSquare(x): sqRoot = int (math.sqrt(x)); return (sqRoot * sqRoot = = x); # Function to count minimum squares that sum to n def cntSquares(n): # ans = 1 if the number is a perfect square if (isSquare(n)): return 1 ; # ans = 2: # we check for each i if n - (i * i) is a perfect # square for i in range ( 1 , int (math.sqrt(n))): if (isSquare(n - (i * i))): return 2 ; # ans = 4 # possible if the number is representable in the form # 4^a (8*b + 7). while (n % 4 = = 0 ): n >> = 2 ; if (n % 8 = = 7 ): return 4 ; # since all the other cases have been evaluated, the # answer can only then be 3 if the program reaches here return 3 ; # Driver Code if __name__ = = '__main__' : print (cntSquares( 12 ) , ""); # This code is contributed by gauravrajput1 |
C#
// C# code for the above approach using System; public class GFG{ // returns true if the input number x is a square number, // else returns false static bool isSquare( int x) { int sqRoot = ( int )Math.Sqrt(x); return (sqRoot * sqRoot == x); } // Function to count minimum squares that sum to n static int cntSquares( int n) { // ans = 1 if the number is a perfect square if (isSquare(n)) { return 1; } // ans = 2: // we check for each i if n - (i * i) is a perfect // square for ( int i = 1; i <= ( int )Math.Sqrt(n); i++) { if (isSquare(n - (i * i))) { return 2; } } // ans = 4 // possible if the number is representable in the form // 4^a (8*b + 7). while (n % 4 == 0) { n >>= 2; } if (n % 8 == 7) { return 4; } // since all the other cases have been evaluated, the // answer can only then be 3 if the program reaches here return 3; } // Driver Code public static void Main(String[] args) { Console.Write(cntSquares(12) + "" ); } } // This code contributed by umadevi9616 |
Javascript
<script> // javascript code for the above approach // returns true if the input number x is a square number, // else returns false function isSquare(x) { var sqRoot = parseInt( Math.sqrt(x)); return (sqRoot * sqRoot == x); } // Function to count minimum squares that sum to n function cntSquares(n) { // ans = 1 if the number is a perfect square if (isSquare(n)) { return 1; } // ans = 2: // we check for each i if n - (i * i) is a perfect // square for ( var i = 1; i <= parseInt( Math.sqrt(n)); i++) { if (isSquare(n - (i * i))) { return 2; } } // ans = 4 // possible if the number is representable in the form // 4^a (8*b + 7). while (n % 4 == 0) { n >>= 2; } if (n % 8 == 7) { return 4; } // since all the other cases have been evaluated, the // answer can only then be 3 if the program reaches here return 3; } // Driver Code document.write(cntSquares(12) + "" ); // This code is contributed by umadevi9616 </script> |
输出
3
时间复杂度：O（sqrt（n）） 空间复杂性：O（1）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
