Dynamic programming: How can I break this down in subproblems?

Question

I'm stuck in this problem and I would need some help:

Given an array arr, in each step, 1, 2 or 5 units have to be incremented to all but one item of the array (same amount of units to all of them). The goal is to find the minimum number of steps to all items to be equal.

First example

arr = [1, 1, 5]

1) [1 (+2), 1 (+2), 5] = [3, 3, 5]
2) [3 (+2), 3 (+2), 5] = [5, 5, 5]

Solution: 2 steps

---

Second example

arr = [2, 2, 3, 7]

1) [2 (+1), 2 (+1), 3, 7 (+1)] = [3, 3, 3, 8]
2) [3 (+5), 3 (+5), 3 (+5), 8] = [8, 8, 8, 8]

Solution: 2 steps

---

I have tried some things but I'm really stuck.

I consider a base case when all items are already equal. In another case, I try to find all the possible solutions by incrementing 1, 2 and 5 to every item but one in the array:

def equal(arr):

    if (allElementsIdentical(arr)):
        return 0

    min = sys.maxsize
    for i in [1, 2, 5]:
        for j in range(len(arr)):

            #Increment all items by "i", except item at index "j"
            newArr = arr.copy()
            for k in range(j):
                newArr[k] += i
            for k in range(j + 1, len(newArr)):
                newArr[k] += i

            movements = 1 + equal(newArr)
            if movements < min:
                min = movements
    return min

This solution doesn't work because recursion never ends. E.g.

[1, 1, 5] -> [1, 2, 6] -> [1, 3, 7] -> [1, 4, 8] -> [1, 5, 9] -> ...

Is it my initial approach correct? How can I break it down in subproblems properly? How can I get the recurrence relation?

(I'm learning Python, so any comment about the syntax is also appreciated)

Answer 1

To me adding 1, 2 or 5 to all but one element seems a lot easier to think about as subtracting 1, 2 or 5 from just one element.

[1, 1, 5] -> 5 - 2 -> 3 - 2

[2, 2, 3, 7] -> 3 - 1 -> 7 - 5

To construct a recurrence, we can use a histogram and consider that to shift any value would cost its frequency in operations. Since we are allowed to reduce by 1, we can easily set a lower-bound for the lowest target we might need to shift all values to. Since the lowest could be reached by any other value, shifting all values down to (lowest-5) (as the HackerRank editorial notes), would involve n more operations than shifting all elements down to the lowest, as we first shift all elements to the lowest, then apply (-5) to each one.

Also noted by the editorial is that the smallest number of operations, k, to shift x to target 0, can be found in O(1) by the greedy

k = x / 5 + (x % 5) / 2 + (x % 5) % 2

Since you've asked to rather try and form a recurrence, under these circumstances, we would be left with solving the coin change problem (coins [5, 2, 1]) for each value in the histogram to reach the target. These are independent: it makes no difference the order by which we apply coin_change to each value to find the number of operations needed, which we then multiply by the value's frequency. Tallying the total operations for all values to reach each target, we choose the least.

Answer 2

We want to replace this problem with one that produces the same answer but will be easier to evaluate.

The trick to making it easier to evaluate with a dynamic programming approach is to have the same results show up in lots of places. And therefore we have to replace equivalent versions of this problem with normalized ones.

For a start, the answer doesn't depend on the order that the elements of the array are in. So we can replace our arrays with arrays sorted from smallest to largest. The operation is now we add x to everything but one, then reorder to canonical form.

Next, the answer doesn't depend on the value of the smallest element. So we can subtract that value from all entries. The operation is now we add x to everything but one, then reorder to canonical form, then subtract the smallest from everything.

This greatly reduces our problem. Enough that a breadth first search has a shot. But we have one more trick to pull. And that trick is that it doesn't matter what order we apply the operations in. And therefore we can apply all of our 5 operations before our 2 operations before our 1 operations. With this trick, we can replace each normalized node with (node, last_operation) and a starting last_operation of 5. The reason why this is a win is that now we have an upper bound for the rest of an A* search. That bound is the current number of steps + sum of ceil(node[i] / last_operation).

And now this can be solved with A* search. Let's do your examples by hand. Using the notation, (total cost, normalized, last_operation, steps).

Example 1: [1, 1, 5]

We normalize to [0, 0, 4] and have a last_operation of 5 and a cost of 0+0+1 = 1. No steps taken. So we start with:

(1, [0, 0, 4], 5)

We take that out, and consider our operations. We get the following for operation 5:

[0, 0, 4] + [5, 5, 0] = [5, 5, 4] => [0, 1, 1] # cost 1 + 0+1+1 = 3
[0, 0, 4] + [5, 0, 5] = [5, 0, 9] => [0, 5, 9] # cost 1 + 0+1+2 = 4
[0, 0, 4] + [0, 5, 5] = [0, 5, 9] => [0, 5, 9] # cost 1 + 0+1+2 = 4 DUP

And for operation 2 we get:

[0, 0, 4] + [2, 2, 0] = [2, 2, 4] => [0, 0, 2] # cost 1 + 0+0+1 = 2
[0, 0, 4] + [2, 0, 2] = [2, 0, 4] => [0, 2, 4] # cost 1 + 0+1+2 = 4
[0, 0, 4] + [0, 2, 2] = [0, 2, 4] => [0, 2, 4] # cost 1 + 0+1+2 = 4 DUP

And for operation 1 we get:

[0, 0, 4] + [1, 1, 0] = [1, 1, 4] => [0, 0, 3] # cost 1 + 0+0+3 = 4
[0, 0, 4] + [1, 0, 1] = [1, 0, 4] => [0, 1, 4] # cost 1 + 0+1+5 = 6
[0, 0, 4] + [0, 1, 1] = [0, 1, 4] => [0, 1, 4] # cost 1 + 0+1+5 = 6 DUP

We stick the 7 non-dups into our priority queue, and the best that comes out looks like this:

(total cost, normalized, last_operation, steps)
(         2,    [0,0,2],              2,     1)

We then try operations 2 and 1 on this, and of course find that one of the outcomes is [0, 0, 0] after 2 steps.