text: Coin Change | DP | Either Pick this coin or not ; else We have no option but to leave this coin ; cin >> tc ;
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; int coinchange ( vector < int > & a , int v , int n , vector < vector < int > > & dp ) { if ( v == 0 ) return dp [ n ] [ v ] = 1 ; if ( n == 0 ) return 0 ; if ( dp [ n ] [ v ] != -1 ) return dp [ n ] [ v ] ; if ( a [ n - 1 ] <= v ) { return dp [ n ] [ v ] = coinchange ( a , v - a [ n - 1 ] , n , dp ) + coinchange ( a , v , n - 1 , dp ) ; } return dp [ n ] [ v ] = coinchange ( a , v , n - 1 , dp ) ; } int32_t main ( ) { int tc = 1 ; while ( tc -- ) { int n , v ; n = 3 , v = 4 ; vector < int > a = { 1 , 2 , 3 } ; vector < vector < int > > dp ( n + 1 , vector < int > ( v + 1 , -1 ) ) ; int res = coinchange ( a , v , n , dp ) ; cout << res << endl ; } }