Overlapping subproblem in a dynamic problem question (Coin change problem)

Question

I am trying to develop a good intuition of Dynamic Programming questions but I am not able to understand a particular aspect of the questions.

I will take an example of Coin Change problem as provided on leetcode https://leetcode.com/problems/coin-change/

In many tutorials, a bottoms-up approach is mentioned such as in this one - https://www.topcoder.com/community/competitive-programming/tutorials/dynamic-programming-from-novice-to-advanced/

In this approach, we start from the optimal solution and then build up the array towards our solution. Example - We find the optimal solution of finding sum 2 then 3 and so on. In the end, we will have our solution. This is the approach which I understand.

I am having trouble wrapping my head around another approach of recursion with memoization. I have written a backtracking approach to the problem but am not sure how to apply memoization to it.

public int changeCoins_BT(int[] coins, int target, int min, int num_curr) {

    if(target == 0) {
        return min < num_curr ? min : num_curr;
    } else if(target < 0) return min;
    else if(num_curr > min) return min;

    for(int i=0;i<coins.length;i++) {
        min = changeCoins_BT(coins,target-coins[i],min,num_curr+1);
    }

    return min;
}

Answer 1

Before finding recursive solution for DP, try identifying sub-problems of the problem in question. Since, each sub problem is same as parent problem and same algorithm will be applied.

Let's take the example for coin change where you are given list of denominations, d[] and sum, S and we need to find minimum number of denominations, count (of denominations) for summing up to S. If we want to define a solution (method) for finding count that would be int findMinDenom(int[] d, int S). At this point we don't know what implementation it would be but we do know what parameters are required for the problem which is d and S.

Keeping in mind that sub-problems would also have same solution but with lower sum. Hence, we try to implement in such way that findMinDenom solves for each of sub-problems. This will lead us to a recursive solution where we call same method with lower sum, s.

int findMinDenom(int[] d, int S) {
  if (S == 0) {
    // If Sum is zero, then no denomination is required.
    return 0;
  }
  int result = Integer.MAX_VALUE; // Define Integer max
  for ( int i = 0; i < d.length; i++) {
    int s = S - d[i] // Reduced to a sub-problem
    // Handle case where s < 0
    if (s < 0) {
      continue;
    }
    int r = findMinDenom(d, s); // Solution for lower sum, s
    result = Math.min(result, r + 1); // Plus 1 because we have just used one denomination.
  }
  return result;
}

We have just solved using DP. However, there is no memoization. We will introduce using array to hold results. Because we don't if a sub-problem has already been solved. If yes, then just return the result of that sub-problem. For sum 0, denomination would be zero. There solution[0] = 0 and we wish to find solution to problem S, in coding terms, solution[S]. Therefore size of solution array is S+1.

// Initialize solution
int[] solution = new int[S+1];
solution[0] = 0; 
for (int i = 1; i <= S; i++)
  solution[i] = -1; // Just to denote that solution is not found yet.

Now, pass solution of our recursive method.

int findMinDenomMemo(int[] d, int S, int[] solution) {
  if (solution[S] > -1) {
    // Solution exists
    return solution[S];
  }
  int result = Integer.MAX_VALUE; // Define Integer max
  for ( int i = 0; i < d.length; i++) {
    int s = S - d[i] // Reduced to a sub-problem
    // Handle case where s < 0
    if (s < 0) {
      continue;
    }
    int r = findMinDenomMemo(d, s, solution); // Solution for lower sum, s
    result = Math.min(result, r + 1); // Plus 1 because we have just used one denomination.
  }
  // Just now solved for sub problem S. So store it.
  solution[S] = result;
  return result;
}