This is a C++ Program that Solves Minimum Number of Squares Problem using Dynamic Programming technique.
It is always possible to represent a number in the form of sum of squares of numbers.
For example – 15= 3^2 + 2^2 + 1^2 + 1^2
Given a number x, find the minimum number of squares whose sum equals to x.
Any number can be represented in the form of sum of squares. The maximum number of squares that sum upto a number x is x(simply adding x times). Now, to find the minimum value we will calculate the results for subproblems in a bottom up fashion. Then, using these values, we will select the best result.
n=19 result=3 (3^2 + 3^2 + 1)
Here is source code of the C++ Program to Solve Minimum Number of Squares Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.
using namespace std;
int minSquares(int x)
//create an array to store results of the sub-problem
//minSq[i]=min. number of squares that sum upto i
//the max. number of squares that sum upto i is equal to i
//select the minimum value for i by using already computed values
cout<<"Enter the number "<<endl;
cout<<"Min. number of squares that sum up to input number are "<<endl;
In the main function, we take input for the number x. We will pass this value to the function minSquares as a parameter. This function will calculate the result using bottom up DP technique and return the result which will be displayed on the standard output.
Case-1: $ g++ min_squares.cpp $ ./a.out Enter the number 100 Min. number of squares that sum up to input number are 1
Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.