Minimum number of squares whose sum equals to given number n | A dynamic programming based C ++ program to find minimum number of squares whose sum is equal to a given number ; Returns count of minimum squares that sum to n ; We need to check base case for n i . e . 0 , 1 , 2 the below array creation will go OutOfBounds . ; Create a dynamic programming table to store sq ; getMinSquares table for base case entries ; getMinSquares rest of the table using recursive formula ; max value is i as i can always be represented as 1 * 1 + 1 * 1 + ... ; Go through all smaller numbers to to recursively find minimum ; Store result and free dp [ ] ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int getMinSquares ( int n ) { if ( n <= 3 ) return n ; int * dp = new int [ n + 1 ] ; dp [ 0 ] = 0 ; dp [ 1 ] = 1 ; dp [ 2 ] = 2 ; dp [ 3 ] = 3 ; for ( int i = 4 ; i <= n ; i ++ ) { dp [ i ] = i ; 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 ] ) ; } } int res = dp [ n ] ; delete [ ] dp ; return res ; } int main ( ) { cout << getMinSquares ( 6 ) ; return 0 ; }