Minimum number of squares whose sum equals to given number n | Returns count of minimum squares that sum to 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 . ; Create a dynamic programming table to store sq ; getMinSquares table for base case entries ; getMinSquares for 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
function getMinSquares ( n ) { if ( n <= 3 ) return n ; var dp = new Array ( n + 1 ) ; dp [ 0 ] = 0 ; dp [ 1 ] = 1 ; dp [ 2 ] = 2 ; dp [ 3 ] = 3 ; for ( var i = 4 ; i <= n ; i ++ ) { dp [ i ] = i ; 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 ] ) ; } } var res = dp [ n ] ; return res ; } document . write ( getMinSquares ( 6 ) ) ;