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?

Kiker

Indeed, i always wonder how do people arrive at such beautiful solutions and how do they arrive when they see such problem the 1st time. memoization using map is intuitive but this is not. – Myth

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

Monteverdi

Beautifully explained. In addition to this, if anybody else is wondering why jth loop iterates from arr[i] till sum, It is because of this part in code j - arr[i-1] < 0 ? 0. You don't need to update the 0 to arr[i] - 1 sum because the arr[i] greater than sum can not contribute to the results. For example: 5 can not contribute to the sum 0,1,2,3 and 4. If sum is 5(jth column), there is one way to get to 5. But with a coin of denomination 5, there are 0 ways to make change for 1,2,3,4. – Kiker

Answer 2

TL;DR: Note that in your 2D recurrence, when computing entries of table[i], you're only using table[i][...] and table[i - 1][...]. This should give you a hint to only store the previous and the current row, and lead you to reduce the space to a 1D array.

---

First, consider a much simpler recurrence to find the Nth Fibonacci number, where we reduce O(N) space to O(1) space:

For the recurrence F(n) = F(n - 1) + F(n - 2)

F[0] = 0
F[1] = 1

for(int i = 2; i <= N; i++) {
    F[i] = F[i - 1] + F[i - 2]
}

return F[N]

Here, we see that we're only using the last 2 values of the recurrence, and do not need the whole array to store all values.

F0 = 0
F1 = 1
Fn = 1

for(int i = 2; i <= N; i++) {
    Fn = F0 + F1
    F0 = F1
    F1 = Fn
}

return Fn

---

We now apply a similar reduction to your problem, just in one higher dimension. Taking your 2D version, we modify it to only store 2 rows table[i - 1] (as tablePrev) and table[i] (as tableI) and keep them updated.

 tablePrev = // Initialised to the 0th row

// All I did was replace table[i - 1][...] with tablePrev[...],
// and table[i][...] with tableI[...]
for (int i = 1; i < arr.length; i++) {
    tableI = tablePrev

    for (int j = 1; j <= sum; j++) {
        int sumWithI = j - arr[i-1] < 0 ? 0 : tableI[j - arr[i-1]];
        int sumWithoutI = tablePrev[j];
        tableI[j] = sumWithI + sumWithoutI;
    }

    tablePrev = tableI
}

That's it. We've reduced the space to a 1-D array - but we're using two arrays. For this particular problem, it is now easy to see that (due to the nature of updates on tableI) you don't even need tablePrev, and can simply re-use tableI, arriving at the final 1D solution you provide in the question.

Pansie

Answer 3

The solution with a 1 dimensional array is just reusing space that you keep in a separate row. This is possible, because those "older" rows are not used again.

Take for example this statement in your code:

int sumWithoutI = table[i - 1][j];

You can verify that this is the last time you will ever read that value. The next time you read a value from the table, it will either have a greater value for i, or -- if it is the same -- a greater value for j. So there is room for "collapsing" all rows together, and overwriting an array value with a new value that really belongs to the next i value (row).

Choate