Dynamic Programming Solution
/* Dynamic Programming Java implementation of Coin
Change problem */
import java.util.Arrays;
class CoinChange
{
static long countWays( int S[], int m, int n)
{
//Time complexity of this function: O(mn)
//Space Complexity of this function: O(n)
// table[i] will be storing the number of solutions
// for value i. We need n+1 rows as the table is
// constructed in bottom up manner using the base
// case (n = 0)
long [] table = new long [n+ 1 ];
// Initialize all table values as 0
Arrays.fill(table, 0 ); //O(n)
// Base case (If given value is 0)
table[ 0 ] = 1 ;
// Pick all coins one by one and update the table[]
// values after the index greater than or equal to
// the value of the picked coin
for ( int i= 0 ; i<m; i++)
for ( int j=S[i]; j<=n; j++)
table[j] += table[j-S[i]];
return table[n];
}
// Driver Function to test above function
public static void main(String args[])
{
int arr[] = { 1 , 2 , 3 };
int m = arr.length;
int n = 4 ;
System.out.println(countWays(arr, m, n));
}
}
// This code is contributed by Pankaj Kumar
Output:
4
Time Complexity: O(mn)
Following is a simplified version of method 2. The auxiliary space required here is O(n) only.
- C++
- Java
- Python
- C#
- PHP
- Javascript
public static int count( int S[], int m, int n )
{
// table[i] will be storing the number of solutions for
// value i. We need n+1 rows as the table is constructed
// in bottom up manner using the base case (n = 0)
int table[]= new int [n+ 1 ];
// Base case (If given value is 0)
table[ 0 ] = 1 ;
// Pick all coins one by one and update the table[] values
// after the index greater than or equal to the value of the
// picked coin
for ( int i= 0 ; i<m; i++)
for ( int j=S[i]; j<=n; j++)
table[j] += table[j-S[i]];
return table[n];
}
Output:
4
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Following is another Top Down DP Approach:
#include <iostream>
#include <climits>
using namespace std;
int coinsExchange( int amt, int *deno, int n, int *dp) {
// base case
if (amt == 0) {
return dp[amt] = 0;
}
if (dp[amt] != -1) {
return dp[amt];
}
// recursive case
int ans = INT_MAX;
for ( int i = 0 ; i < n ; i++) {
if (amt >= deno[i]) {
int sa = coinsExchange(amt - deno[i], deno, n, dp);
if (sa != INT_MAX) {
ans = min(sa + 1, ans);
}
}
}
return dp[amt] = ans;
}
int main() {
int deno[4] = {1, 2, 5, 10};
int amt = 50;
int *dp = new int [amt + 1];
for ( int i = 0 ; i <= amt ; i++) {
dp[i] = -1;
}
cout << coinsExchange(amt, deno, 4, dp) << endl;
return 0;
}
Time Complexity: O(M*N)
Space Complexity: O(N)