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
< ? php $ dp = array_fill ( 0 , 501 , array_fill ( 0 , 501 , array_fill ( 0 , 5 , -1 ) ) ) ; function countWaysUtil ( $ n , $ parts , $ nextPart ) { global $ dp ; if ( $ parts == 0 && $ n == 0 ) return 1 ; if ( $ n <= 0 $ parts <= 0 ) return 0 ; if ( $ dp [ $ n ] [ $ nextPart ] [ $ parts ] != -1 ) return $ dp [ $ n ] [ $ nextPart ] [ $ parts ] ; for ( $ i = $ nextPart ; $ i <= $ n ; $ i ++ ) $ ans += countWaysUtil ( $ n - $ i , $ parts - 1 , $ i ) ; return ( $ dp [ $ n ] [ $ nextPart ] [ $ parts ] = $ ans ) ; } function countWays ( $ n ) { return countWaysUtil ( $ n , 4 , 1 ) ; } $ n = 8 ; echo countWays ( $ n ) ; ? >