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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int dp [ 5001 ] [ 5001 ] [ 5 ] ; 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 ) ; } int countWays ( int n ) { memset ( dp , -1 , sizeof ( dp ) ) ; return countWaysUtil ( n , 4 , 1 ) ; } int main ( ) { int n = 8 ; cout << countWays ( n ) << endl ; return 0 ; }