Count of strings that can be formed using a , b and c under given constraints | C ++ program to count number of strings of n characters with ; n is total number of characters . bCount and cCount are counts of ' b ' and ' c ' respectively . ; Base cases ; if we had saw this combination previously ; Three cases , we choose , a or b or c In all three cases n decreases by 1. ; A wrapper over countStrUtil ( ) ; Driver code ; Total number of characters
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countStrUtil ( int dp [ ] [ 2 ] [ 3 ] , int n , int bCount = 1 , int cCount = 2 ) { if ( bCount < 0 cCount < 0 ) return 0 ; if ( n == 0 ) return 1 ; if ( bCount == 0 && cCount == 0 ) return 1 ; if ( dp [ n ] [ bCount ] [ cCount ] != -1 ) return dp [ n ] [ bCount ] [ cCount ] ; int res = countStrUtil ( dp , n - 1 , bCount , cCount ) ; res += countStrUtil ( dp , n - 1 , bCount - 1 , cCount ) ; res += countStrUtil ( dp , n - 1 , bCount , cCount - 1 ) ; return ( dp [ n ] [ bCount ] [ cCount ] = res ) ; } int countStr ( int n ) { int dp [ n + 1 ] [ 2 ] [ 3 ] ; memset ( dp , -1 , sizeof ( dp ) ) ; return countStrUtil ( dp , n ) ; } int main ( ) { int n = 3 ; cout << countStr ( n ) ; return 0 ; }