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
using System ; class GFG { static int [ , , ] dp = new int [ 5001 , 5001 , 5 ] ; static int countWaysUtil ( int n , int parts , int 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 ( int i = nextPart ; i <= n ; i ++ ) ans += countWaysUtil ( n - i , parts - 1 , i ) ; return ( dp [ n , nextPart , parts ] = ans ) ; } static int countWays ( int n ) { for ( int i = 0 ; i < 5001 ; i ++ ) { for ( int j = 0 ; j < 5001 ; j ++ ) { for ( int l = 0 ; l < 5 ; l ++ ) dp [ i , j , l ] = - 1 ; } } return countWaysUtil ( n , 4 , 1 ) ; } public static void Main ( String [ ] args ) { int n = 8 ; Console . WriteLine ( countWays ( n ) ) ; } }