Java:: Coin Change Problem - dynamic programming - memoization - recursion

Problem: We have a series of coins, eg. 1, 3, 5 and we're trying to find the least possible number coins to sum up to a value, eg. 11 The smallest possible solution is 3 coins (5+5+1, 5+3+3).

Solution: The Greedy algorithm only works in special cases, but we're trying to find the ultimate, smallest and fast solution.

The goal is to check all possibilities, which can take a lot of time, if we don't use memoization. The solution below is a recursive function with two arguments:

• int[] k - table of coins (1, 3, 5) ordered ascending
• int val - the value we wish to solve

Read the comments for more information

 public static Hashtable<Integer, Integer> solved = new Hashtable<Integer, Integer>();
 
 public static int kovanci(int[] k, int val) {
  // we've reached the end of recursion - a leaf
  // if the value is less than zero it means that the current combination is not solvable
  // if the value is zero, it means it is solvable
  if (val <= 0) return val;

  // for as many coins try to decrease the value for the coin value 
  // and try to solve the smaller problem
  int min = -1; //default: if it's not solvable
  for (int i = k.length - 1; i >= 0; i--) {
   
   // if the coin k[i] exists in the solution, it means the solution is
   // solutions(value - coin_value) + 1
   // eg. we have coins: 1, 3, 5 and the value is 11
   // if the coin 5 exists in the solution, try to solve the problem for value 11-5 = 6
   // the solution is smaller_solution + 1
   int newVal = val - k[i];
   int r;

   // dynamic programming - memoization
   // if we already have the minimum for the new value, fetch it (with time complexity O(1)), 
   // so that we don't recursively re-solve the problem and waste time
   if (solved.get(newVal) != null) {
    //solution = smaller_sollution + 1
    r = solved.get(newVal) + 1;
   } else {
    //try to solve the smaller problem
    r = kovanci(k, newVal);
    //if the solution is valid, the new solution is smaller_solution + 1
    if (r >= 0) r++;
    //else, keep the negative value - it means that it's not valid
    //eg: coins 3, 5, value 11 is not solvable, the solution is -1
   }
   // from all of the solutions, get the minimum value
   // and skip invalid solutions ( less than zero )
   if ((r > 0) && (min == -1 || r < min)) {
    min = r;
   }
  }
  // dynamic programming - memoization
  // once we do get the smallest possible solution, save it for later use
  // it saves A LOT of time and useless work, that's already been done
  solved.put(val, min);
  return min;
 }