Dynamic programming: max sum through a 2-D matrix(a harder version)

Question

It's from my algorithm class and I think I really need some help.

Given a cost matrix Happiness[][] where Happiness[i][j] denotes the happiness of visiting cell with coordinates (i,j), you start from top right corner and ends at bottom left corner. We want to find max happiness.
You can only go down or go left in the matrix.

But we have 2 constraints here:
1.you can choose to skip zero or more rows which mean you can go to the last row at first if you want.
2.When you choose to go left, cost = cost - 1. The second consecutive left causes cost = cost - 2, but when you go down then go left, it refreshes. Here is an example:

This is the step:

I am not sure I am right or wrong. I use top down. My solution: To reach a cell matrix[i][j], you must have come from one cell higher or left to the original cell.

My recurrence:(I stuck here) I think the base cases are leftmost row and bottommost column.
How can computer check the consecutive steps and know is an opt solution?

I know it's strange to post the whole question, but I can not simplify the question better...

Answer 1

In agreement with @גלעד ברקן's comment, the trick to solving this problem is adding an extra dimension representing the number of lefts taken to reach the cell to the recurrence relation.

Note: to make this problem easier, I have reversed the rows of the given matrix so that the allowed movement directions are down and right, and the starting cell becomes (0, 0) and the ending cell becomes (W - 1, H - 1), where W and H are the width and height of the matrix respectively. Also, the matrix and the corresponding max happiness dp table are considered to be in row major order, i.e. matrix[y][x] is the value at the cell (x, y).

Our true base case is the happiness of visiting the starting cell, which is either matrix[0][0] or 0, depending on whether the value of the starting cell has to be included in the total happiness. However, we also have two pseudo base cases are quite simpler to calculate compared to the actual recursion.

These pseudo base cases are the leftmost column (remember, the rows have been reversed, so this is the rightmost column in the original matrix) and the topmost row. The recurrence relation for a cell (0, y) (1 <= y < H) in the leftmost column is:

h[y][0][0] = matrix[y][0] + max(h[i][0][0] for i in 0 to y-1)

Where h is our max happiness dp table and h[y][x][r] is the max happiness gained on going from cell (0, 0) to (x, y) (following the given rules) having taken r consecutive rights (or lefts, for the original non row-reversed matrix) just before arriving at (x, y). Thus, if r is 0, the last traversed cell was one directly above the current cell. The only possible way to reach a cell in the leftmost column is to come from a cell directly above it.

An important thing to note about our max happiness table is that the maximum happiness for any cell (x, y) is given by the maximum of h[y][x][r] for all values of r. If h is a three-dimensional array/list, it can also be represented as max(h[y][x]).

Similarly, the recurrence relation for a cell (x, 0) (1 <= x < W) in the topmost row is:

h[0][x][x] = h[0][x-1][x-1] + matrix[0][x] - x

This stems from the fact that the only way to reach a cell in the topmost row is to keep going right from the starting cell. The number of rights taken to reach a cell in the topmost row is equal to its 0-based X-coordinate, hence the penalty of -x.

Now that we have our base cases, we can move on to the recurrence relation for a cell (x, y), where 1 <= x < W and 1 <= y < H.

While estabilishing this recurrence relation, the first thing to note is that there are only two possibilities: either the last cell was above or to the left of the given cell. We shall consider both these possibilities.

If the last cell was above the given cell, it would have the coordinates (x, j), where 0 <= j < y. For maximum happiness, the happiness at the last cell must also be maximum. Thus, the maximum happiness at (x, y) when the last cell is above the given cell is given by

h[y][x][0] = matrix[y][x] + max(max(h[j][x]) for j in 0 to y-1)

Note that the number of rights made (r) is 0, and max(h[j][x]) is the maximum happiness obtained on reaching the cell (x, j) with any number of rights.

If the last cell was to the left of the given cell (or in other words, the last move was to the right), its coordinates would simply be (x - 1, y). This is because we can move only one cell to the right at a time. Unlike the previous case, the last cell position is constant. However, the number of consecutive rights (r) taken to reach this cell is variable. Therefore, we must consider all possible values for r. Since a minimum of 1 right and a maximum of x rights can be made, 1 <= r <= x. For each value of r, the maximum happiness of this cell is the maximum happiness of the cell to the left (the last cell) for r - 1 rights plus the value at (x, y) minus the penalty (which is just r - 1). In pseudocode,

for r in 1 to x:
    h[y][x][r] = h[y][x-1][r-1] + matrix[y][x] - r

We now have everything we need to run the algorithm in a bottom-up or a top-down approach. Our final answer, the maximum happiness taken to reach the bottom-right (bottom-left, for the original non-row-reversed matrix) cell, is given by max(h[H-1][W-1]).

Putting everything together, we have the following (Python-esque) bottom-up algorithm with a time complexity of O(W^2 * H^2) algorithm:

h[0][0][0] = matrix[0][0]

for x in range(1, W):
    h[0][x][x] = h[0][x-1][x-1] + matrix[0][x] - x

for y in range(1, H):
    h[y][0][0] = matrix[y][0] + max(h[i][0][0] for i in range(y))

for y in range(1, H):
    for x in range(1, W):
        for r in range(1, x + 1):
            h[y][x][r] = h[y][x-1][r-1] + matrix[y][x] - r
        h[y][x][0] = matrix[y][x] + max(max(h[j][x]) for j in range(y))

return max(h[H-1][W-1])

On closer inspection, it appears that the O(W) operation of computing max(h[j][x]) can be removed by precalculating it, making the final time complexity O(W * H^2). Note that this optimization is valid only for the bottom-up approach. This works because the cell (x, j) (where j < y) should have already been visited in the bottom-up approach. In the code below, max(h[y][x]) is stored in h[y][x][W].

The full, optimized version of the bottom-up algorithm in Python 3 (including the given example matrix as input and row-reversal of the input matrix):

matrix = [[5, -2, -1, 5, 3, -99, 4, 0],
[5, -2, -1, -3, 3, -99, 2, -3],
[-98, -98, -98, -98, -98, -98, -98, -98],
[-99, -99, -99, -99, -99, -99, -99, -99],
[5, 0, -3, 5, -1, 7, -2, 2],
[1, 2, 7, 0, 0, 1, -1, -1]]

H = len(matrix)
W = len(matrix[0])

for row in matrix:
    row.reverse()

h = [[[0] * (W + 1) for i in range(W)] for j in range(H)]

h[0][0][0] = matrix[0][0]
h[0][0][W] = h[0][0][0]

for x in range(1, W):
    h[0][x][x] = h[0][x-1][x-1] + matrix[0][x] - x
    h[0][x][W] = h[0][x][x]

for y in range(1, H):
    h[y][0][0] = matrix[y][0] + max(h[i][0][0] for i in range(y))
    h[y][0][W] = h[y][0][0]

for y in range(1, H):
    for x in range(1, W):
        h[y][x][0] = matrix[y][x] + max(h[j][x][W] for j in range(y))
        h[y][x][W] = h[y][x][0]
        for r in range(1, x + 1):
            h[y][x][r] = h[y][x-1][r-1] + matrix[y][x] - r
            h[y][x][W] = max(h[y][x][W], h[y][x][r])

print(h[H-1][W-1][W])