Hi, In this blog I tried to provide an efficient solution for a famous coin exchange problem using dynamic problem in bottom up approach whose time complexity is O(mn).

Problem Definition

In coin exchange problem you can think of a coin vending machine of a Bank having abundant supply of coins which returns back coins in exchange to the note put into it by the people, In that case machine will return coins, sum of which will amount the same value put into the machine, here order doesn't matter ( i.e. {1,2,2} ,{2,1,2}, {2,2,1} will be consider as same ).
Now the problem is that, you have to find the total number of solution in which you can perform this operation.

For example : 

Suppose the machine has infinite supply of 1, 2, 3 rupees coins.
One person came and want exchange for a 5 rupees note. 
Now machine can return his money in form of 
{1,1,1,1,1} rupees coin 
{1,1,1,2}    rupees coin
{1,2,2}       rupees coin
{5}             rupees coin

so there are 4 ways to do this.

You can read more about this problem here https://en.wikipedia.org/wiki/Change-making_problem

Java solution for the above problem using bottom up approach

package com.tech.blog;

import java.util.Scanner;

public class CoinExchangeProblem {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n;
		int x;
		int y;
		int sum;

		//Final sum of the value in return of which coins are being given 
		System.out.print("Enter the final sum to be formed using coins : ");
		sum = sc.nextInt();

		//For the count of set of coins ( count of different values of coins )
		System.out.print("Enter total number of coins : ");
		n = sc.nextInt();
		
		int[] coin = new int[n];

		// To input the values of coins for our problem
		System.out.print("Enter values of coins : ");
		for (int i = 0; i < n; i++)
			coin[i] = sc.nextInt();
		sc.close();

		// We need sum + 1 rows as the table is constructed in bottom up manner using 
	    // the base case 0 value case (n = 0)
		int[][] solution = new int[sum + 1][n];
		
		//Base case fill all the entries for 0 value case (n = 0)
		for (int i = 0; i < n; i++)
			solution[0][i] = 1;
		
		// Filling the table entries in bottom up manner
		for (int i = 1; i < sum + 1; i++) {
			for (int j = 0; j < n; j++) {
				// number of solutions including coin[j]
				x = (i - coin[j] >= 0) ? solution[i - coin[j]][j] : 0;

				// number of solutions excluding coin[j]
				y = (j >= 1) ? solution[i][j - 1] : 0;

				// total number of solution
				solution[i][j] = x + y;
			}
		}
		System.out.println("Total solutions for your problem is "
				+ solution[sum][n - 1]);
		return;
	}
}

Output of the above code

Enter the final sum to be formed using coins :4
Enter total number of coins :3
Enter values of coins :123
Total solutions for your problem is 4