ChangeDP.java

import java.util.Scanner;

public class ChangeDP 
{ 
    /* 
    * The idea is to break down the problem into smaller sub problem:
    * Finding minimun change for m can be broken down into sub problems of finding minimum change for each input from
    * 1 to m
    * The bottom up approach
    */ 
    private static int getChange(int m) 
    {
        int[] denominations = { 1, 3, 4 };
      
        /* Step - 1 We need to create memo for memoization. 
        * Memo will hold the best solution for each input from 0 to m and 
        * In another sense, it holds solution for each smaller sub problem.
        */ 
        int[] memo = new int[m + 1];

        // Best value for zero change is always zero, this is our start condition.
        // m[i] represents the least number of coins requires that constitue to element at m[i], hence the best solution.
        memo[0] = 0;

        for(int i = 1; i <= m; i++)
        {
        	memo[i] = Integer.MAX_VALUE;
        }

        // Now we iterate through each value from 1 - m finding answers to each sub problem.
 
        for(int i = 1; i <= m ; i++)
        {
        	for(int j = 0; j < denominations.length; j++)
        	{
        		// This difference leads to a value which we must have already previously solved and need to extract from our memo.
        		int difference = i - denominations[j];

        		if(difference >= 0)
        		{
        			// We add + 1 signifying the current coin addition to previous best solution.
        			memo[i] = Math.min(memo[i], memo[difference] + 1);
        		}
        	}
        }
        return memo[m];
    }

    public static void main(String[] args) 
    {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        System.out.println(getChange(m));
    }
}