Count different numbers that can be generated such that there digits sum is equal to ' n ' | Function to count ' num ' as sum of digits ( 1 , 2 , 3 , 4 ) ; Initialize dp [ ] array ; Base case ; Initialize the current dp [ ] array as '0' ; if i == j then there is only one way to write with element itself ' i ' ; If j == 1 , then there exist two ways , one from '1' and other from '4' ; if i - j is positive then pick the element from ' i - j ' element of dp [ ] array ; Check for modulas ; return the final answer ; Driver code
< ? php function countWays ( $ num ) { $ dp [ $ num + 1 ] = array ( ) ; $ MOD = 100000000 + 7 ; $ dp [ 1 ] = 2 ; for ( $ i = 2 ; $ i <= $ num ; ++ $ i ) { $ dp [ $ i ] = 0 ; for ( $ j = 1 ; $ j <= 3 ; ++ $ j ) { if ( $ i - $ j == 0 ) $ dp [ $ i ] += 1 ; else if ( $ j == 1 ) $ dp [ $ i ] += $ dp [ $ i - $ j ] * 2 ; else if ( $ i - $ j > 0 ) $ dp [ $ i ] += $ dp [ $ i - $ j ] ; if ( $ dp [ $ i ] >= $ MOD ) $ dp [ $ i ] %= $ MOD ; } } return $ dp [ $ num ] ; } $ n = 3 ; echo countWays ( $ n ) ; ? >