Skip to content

Instantly share code, notes, and snippets.

@warlock2k
Created May 28, 2020 03:45
Show Gist options
  • Save warlock2k/3bea9f22b14441d4c0456df8b1a5fd34 to your computer and use it in GitHub Desktop.
Save warlock2k/3bea9f22b14441d4c0456df8b1a5fd34 to your computer and use it in GitHub Desktop.
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));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment