Thought process for arriving at dynamic programming solution of Coins change problem

Question

I am learning dynamic programming and came across this famous coins change problem.

The reccurence relation to solve this problem is given by

countCoinsChangeRec(arr, sum - arr[i], i) + countCoinsChangeRec(arr, sum, i - 1);

The simplest way to optimize the problem is by storing the solutions of sub problem. So I maintained a Map for each value of (sum,i). There by not solving same problems again.

        String key = sum + ":" + i;    
        Integer memoizedVal = results.get(key);
        if (memoizedVal != null) {
            return memoizedVal;
        }

Next level of optimization is having a 2D table of n X sum where n is number of elements in the set.

It is easily understandable from reccurence relation that (arr, sum - arr[i], i) translates to DP[sum-arr[i]] in same row.(Because i is same)

And (arr, sum, i - 1) translates to DP[i-1] (Previous row in sum column).

Complete solution with 2D matrix shown below.

public static int countWaysDP2D(int[] arr, int sum) {
    int[][] table = new int[arr.length][sum + 1];
    table[0][0] = 1;

    for (int i = 1; i <= sum; i++) {
        table[0][i] = 0;
    }

    for (int j = 1; j < arr.length; j++) {
        table[j][0] = 1;
    }

    for (int i = 1; i < arr.length; i++) {
        for (int j = 1; j <= sum; j++) {
            int sumWithI = j - arr[i-1] < 0 ? 0 : table[i][j - arr[i-1]];
            int sumWithoutI = table[i - 1][j];
            table[i][j] = sumWithI + sumWithoutI;
        }
    }
    return table[arr.length - 1][sum];
}

But the soultion given here in method 2 uses just 1D array as shown below

public static int countWaysDP1D(int[] arr, int sum) {
    int[] table = new int[sum + 1];
    table[0] = 1;

    for (int i = 0; i < arr.length; i++) {
        for (int j = arr[i]; j <= sum; j++) {
            table[j] += table[j - arr[i]];
        }
    }
    return table[sum];
}

What is the logic behind using just 1D array? I tested with many input values and results were same as 2D array. How is 2D array solution converted to 1D array?

I mean where are all the initial conditions gone?(0th row and 0th column)

For jth for loop, why does it iterate from jth element in the array till sum incremented by 1? It is really hard to visualize all of that. Can somebody explain this transformation step by step?

Answer 1

From the recurrence relation countCoinsChangeRec(arr, sum - arr[i], i) + countCoinsChangeRec(arr, sum, i - 1);, it is obvious that you need 2D array/table of size len(arr) x (sum+1) to store the results. We shall fill the table sequentially from top left of the table to bottom right and our answer is the value of bottom right cell. You need two values to fill each cell of the table table[i, sum - arr[i]] and table[i - 1, sum].

Consider filling a row -- 0th cell has value 1 and all other cells have a value of 0 at the start. To update a cell we need to lookup table[i, sum - arr[i]] which is within the same row. For table[i - 1, sum], we need to lookup the previous row. We don't need any other rows. So actually we only need 2 rows of space and we can alternatively treat one of the rows as previous row and other as current row being filled.

Now consider using 2 x (sum+1) table with just 2 rows to solve the problem. Consider row 1 is the current row being filled and row 0 is previous row which was already filled. Say arr = [2, 3, 7]. So you fill the row 1 as follows.

table[1, 0] = table[0, 0]  
table[1, 1] = table[0, 1]
table[1, 2] = table[0, 2]
table[1, 3] = table[1, 0] + table[0, 3]
table[1, 4] = table[1, 1] + table[0, 4]
table[1, 5] = table[1, 2] + table[0, 5]
...

After observing above equations, another way to calculate the row 1 is copying row 0 onto unfilled row 1 and then filling row 1 as follows

Copy row 0 onto row 1

table[1, 3] += table[1, 0]
table[1, 4] += table[1, 1]
table[1, 5] += table[1, 2]

Instead of copying row 0 onto unfilled row 1, we can re-use row 0 itself. So the final space efficient avatar of the algorithm is - take a single row of size (sum+1). Assign row[0] = 1 as base condition. There is no difference in how we fill 0th row or any other row because the only lookups we make now is within the same row as shown above.

// Pseudo code
create row of size (sum+1) 

row[0] = 1 // base condition

fill rest of the row with zeros

for element in arr:   /* for (int i = 0; i < arr.length; i++) */
    from column j where j - element >= 0 to end of row /* int j = arr[i]; j <= sum; j++ */
    row[j] += row[j-element]

return last element of row