Count the number of ways to divide N in k groups incrementally | DP Table ; Function to count the number of ways to divide the number N in groups such that each group has K number of elements ; Base Case ; if N is divides completely into less than k groups ; If the subproblem has been solved , use the value ; put all possible values greater equal to prev ; Function to count the number of ways to divide the number N in groups ; Initialize DP Table as - 1 ; Driver Code
let dp = new Array ( 500 ) ; for ( let i = 0 ; i < 500 ; i ++ ) { dp [ i ] = new Array ( 500 ) ; for ( let j = 0 ; j < 500 ; j ++ ) { dp [ i ] [ j ] = new Array ( 500 ) ; for ( let k = 0 ; k < 500 ; k ++ ) dp [ i ] [ j ] [ k ] = 0 ; } } function calculate ( pos , prev , left , k ) { if ( pos == k ) { if ( left == 0 ) return 1 ; else return 0 ; } if ( left == 0 ) return 0 ; if ( dp [ pos ] [ prev ] [ left ] != - 1 ) return dp [ pos ] [ prev ] [ left ] ; let answer = 0 ; for ( let i = prev ; i <= left ; i ++ ) { answer += calculate ( pos + 1 , i , left - i , k ) ; } return dp [ pos ] [ prev ] [ left ] = answer ; } function countWaystoDivide ( n , k ) { for ( let i = 0 ; i < 500 ; i ++ ) { for ( let j = 0 ; j < 500 ; j ++ ) { for ( let l = 0 ; l < 500 ; l ++ ) dp [ i ] [ j ] [ l ] = - 1 ; } } return calculate ( 0 , 1 , n , k ) ; } let N = 8 ; let K = 4 ; document . write ( countWaystoDivide ( N , K ) ) ;