Count number of ways to divide a number in 4 parts | A Dynamic Programming based solution to count number of ways to represent n as sum of four numbers ; " parts " is number of parts left , n is the value left " nextPart " is starting point from where we start trying for next part . ; Base cases ; If this subproblem is already solved ; Count number of ways for remaining number n - i remaining parts " parts - 1" , and for all part varying from ' nextPart ' to 'n ; Store computed answer in table and return result ; This function mainly initializes dp table and calls countWaysUtil ( ) ; Driver Code
dp = [ [ [ - 1 for i in range ( 5 ) ] for i in range ( 501 ) ] for i in range ( 501 ) ] NEW_LINE def countWaysUtil ( n , parts , nextPart ) : NEW_LINE INDENT if ( parts == 0 and n == 0 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( n <= 0 or parts <= 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( dp [ n ] [ nextPart ] [ parts ] != - 1 ) : NEW_LINE INDENT return dp [ n ] [ nextPart ] [ parts ] NEW_LINE DEDENT DEDENT ' NEW_LINE INDENT for i in range ( nextPart , n + 1 ) : NEW_LINE INDENT ans += countWaysUtil ( n - i , parts - 1 , i ) NEW_LINE DEDENT dp [ n ] [ nextPart ] [ parts ] = ans NEW_LINE return ( ans ) NEW_LINE DEDENT def countWays ( n ) : NEW_LINE INDENT return countWaysUtil ( n , 4 , 1 ) NEW_LINE DEDENT n = 8 NEW_LINE print ( countWays ( n ) ) NEW_LINE