Coin Change | DP | Java program for the above approach ; Either Pick this coin or not ; else We have no option but to leave this coin ; Driver code
import java . util . * ; class GFG { static int coinchange ( int [ ] a , int v , int n , 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 ) ; } public static void main ( String [ ] args ) { int tc = 1 ; while ( tc != 0 ) { int n , v ; n = 3 ; v = 4 ; int [ ] a = { 1 , 2 , 3 } ; int [ ] [ ] dp = new int [ n + 1 ] [ v + 1 ] ; for ( int [ ] row : dp ) Arrays . fill ( row , - 1 ) ; int res = coinchange ( a , v , n , dp ) ; System . out . println ( res ) ; tc -- ; } } }