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 program
let dp = new Array ( 5001 ) ; for ( let i = 0 ; i < 5001 ; i ++ ) { dp [ i ] = new Array ( 5001 ) ; for ( let j = 0 ; j < 5001 ; j ++ ) { dp [ i ] [ j ] = new Array ( 5 ) ; } } function countWaysUtil ( n , parts , nextPart ) { 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 ( let i = nextPart ; i <= n ; i ++ ) ans += countWaysUtil ( n - i , parts - 1 , i ) ; return ( dp [ n ] [ nextPart ] [ parts ] = ans ) ; } function countWays ( n ) { for ( let i = 0 ; i < 5001 ; i ++ ) { for ( let j = 0 ; j < 5001 ; j ++ ) { for ( let l = 0 ; l < 5 ; l ++ ) dp [ i ] [ j ] [ l ] = - 1 ; } } return countWaysUtil ( n , 4 , 1 ) ; } let n = 8 ; document . write ( countWays ( n ) ) ;