Minimum number of cubes whose sum equals to given number N | Python implementation of the approach ; Function to return the minimum number of cubes whose sum is k ; While current perfect cube is less than current element ; If i is a perfect cube ; i = ( i - 1 ) + 1 ^ 3 ; Next perfect cube ; Re - initialization for next element ; Driver code
import sys NEW_LINE def MinOfCubedDP ( k ) : NEW_LINE INDENT DP = [ 0 ] * ( k + 1 ) ; NEW_LINE j = 1 ; NEW_LINE t = 1 ; NEW_LINE DP [ 0 ] = 0 ; NEW_LINE for i in range ( 1 , k + 1 ) : NEW_LINE INDENT DP [ i ] = sys . maxsize ; NEW_LINE while ( j <= i ) : NEW_LINE INDENT if ( j == i ) : NEW_LINE INDENT DP [ i ] = 1 ; NEW_LINE DEDENT elif ( DP [ i ] > DP [ i - j ] ) : NEW_LINE INDENT DP [ i ] = DP [ i - j ] + 1 ; NEW_LINE DEDENT t += 1 ; NEW_LINE j = t * t * t ; NEW_LINE DEDENT t = j = 1 ; NEW_LINE DEDENT return DP [ k ] ; NEW_LINE DEDENT num = 15 ; NEW_LINE print ( MinOfCubedDP ( num ) ) ; NEW_LINE