Ways to arrange Balls such that adjacent balls are of different types | PHP program to count number of ways to arrange three types of balls such that no two balls of same color are adjacent to each other ; table to store to store results of subproblems ; Returns count of arrangements where last placed ball is ' last ' . ' last ' is 0 for ' p ' , 1 for ' q ' and 2 for ' r ' ; if number of balls of any color becomes less than 0 the number of ways arrangements is 0. ; If last ball required is of type P and the number of balls of P type is 1 while number of balls of other color is 0 the number of ways is 1. ; Same case as above for ' q ' and ' r ' ; If this subproblem is already evaluated ; if last ball required is P and the number of ways is the sum of number of ways to form sequence with ' p - 1' P balls , q Q Balls and r R balls ending with Q and R . ; Same as above case for ' q ' and ' r ' ; else ( last == 2 ) ; Returns count of required arrangements ; Three cases arise : return countWays ( $p , $q , $r , 0 ) + Last required balls is type P countWays ( $p , $q , $r , 1 ) + Last required balls is type Q countWays ( $p , $q , $r , 2 ) ; Last required balls is type R ; Driver code
< ? php $ MAX = 100 ; $ dp = array_fill ( 0 , $ MAX , array_fill ( 0 , $ MAX , array_fill ( 0 , $ MAX , array_fill ( 0 , 3 , -1 ) ) ) ) ; function countWays ( $ p , $ q , $ r , $ last ) { global $ dp ; if ( $ p < 0 $ q < 0 $ r < 0 ) return 0 ; if ( $ p == 1 && $ q == 0 && $ r == 0 && $ last == 0 ) return 1 ; if ( $ p == 0 && $ q == 1 && $ r == 0 && $ last == 1 ) return 1 ; if ( $ p == 0 && $ q == 0 && $ r == 1 && $ last == 2 ) return 1 ; if ( $ dp [ $ p ] [ $ q ] [ $ r ] [ $ last ] != -1 ) return $ dp [ $ p ] [ $ q ] [ $ r ] [ $ last ] ; if ( $ last == 0 ) $ dp [ $ p ] [ $ q ] [ $ r ] [ $ last ] = countWays ( $ p - 1 , $ q , $ r , 1 ) + countWays ( $ p - 1 , $ q , $ r , 2 ) ; else if ( $ last == 1 ) $ dp [ $ p ] [ $ q ] [ $ r ] [ $ last ] = countWays ( $ p , $ q - 1 , $ r , 0 ) + countWays ( $ p , $ q - 1 , $ r , 2 ) ; $ dp [ $ p ] [ $ q ] [ $ r ] [ $ last ] = countWays ( $ p , $ q , $ r - 1 , 0 ) + countWays ( $ p , $ q , $ r - 1 , 1 ) ; return $ dp [ $ p ] [ $ q ] [ $ r ] [ $ last ] ; } function countUtil ( $ p , $ q , $ r ) { } $ p = 1 ; $ q = 1 ; $ r = 1 ; print ( countUtil ( $ p , $ q , $ r ) ) ; ? >