I am new to backtracking and recursion. I have seen numerous explanations on how on to find the minimum number of coins needed to make a particular amount. This involves a top down dynamic approach with mermoization and a bottom up using dynamic programming. Even the brute force apporach always starts using a top down approach breaking the problem down into smaller sub problems and then caching.
However, I have written the following algorithm that is not optimized to do the same but cannot figure out how to apply memoization. Is it even possible?
My basic algorithm is I start from sum = 0 and keep count of how many coins I have used by adding coin values and then returning the minimum count.
//function is called with sum = 0, coins = 0 and minCoins = Integer.MAX_VALUE
//coins[] contains the different coin denominations and target is the desired amount
// count is the number of coins that have been used
public static int makeChangeBacktracking(int sum, int[] coins, int target, int count, int minCoins) {
if(sum == target) {
return count;
}
for(int coin : coins) {
//choose
sum+= coin;
//explore
if(sum <= target) { //if it is greater than the target then why recurse???
int c = makeChangeBacktracking(sum, coins, target, count + 1, minCoins);
if(minCoins > c) {
minCoins = c;
}
//undo
sum-= coin;
}
}
return minCoins;
}
I would like to apply any technique to improve the run time of the above algorithm. A clear explanation of whether or not memoization or other optimization techniques can be applied to this to speed up would be helpful.