Minimum number of squares whose sum equals to given number n | Returns count of minimum squares that sum to n ; 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 recursively find minimum ; Store result and free dp [ ] ; Driver Code
< ? php function getMinSquares ( $ n ) { $ dp ; $ dp [ 0 ] = 0 ; $ dp [ 1 ] = 1 ; $ dp [ 2 ] = 2 ; $ dp [ 3 ] = 3 ; for ( $ i = 4 ; $ i <= $ n ; $ i ++ ) { $ dp [ $ i ] = $ i ; 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 ] ) ) ; } } $ res = $ dp [ $ n ] ; return $ res ; } echo getMinSquares ( 6 ) ; ? >