How can you find the maximum possible sum of values by optimally placing tiles in a matrix rxc where each cell has an integer value?
The goal is to maximize the sum by covering cells with 1x2 or 2x1 tiles.
Consider location (n, k)
, we have 3 cases:
For example:
Case 1:
????
????
??xx
Case 2:
????
???x
???x
Case 3:
????
????
???.
For case 2, we will record which grid in the next line we have already taken so that we can solve this question by dp.
We can define:
sol(x, y, right_incomplete, up_incompletes)
is the maximum of point(x, y) in the condition of right_incomplete and up_incomples
So for point (x, y)
:
if right_incomplete
(which means we a place 1*2 tile in (x, y+1)
), we must close this tile at (x, y)
if up_incomplete
(which means we a place 2*1 tile in (x+1, y)
), we must close this tile at (x, y)
if both right_incomplete
and up_incomplete
, means no feasible solution.
If it is not right_incomplete
and up_incomplete
, we have three choices: place 1 * 2, place 2 * 1, or do nothing. With each choice, we will come to a smaller question.
We take an example:
The Red lines mean the up_incompletes which have k
grids.
The Blue line means the right_incomplete.
The arrows mean there is an incomplete otherwise no.
Now, we are considering the dark gray grid. Based on our up_incompletes
information, we should close this incomplete at this grid, so we have only 1 choice here.
After we do that, then we come to:
We take another example:
Since there is no incomplete from this grid, we have three choices, which are:
Choice 1, do nothing:
Choice 2, place a 1 * 2 tile, so there will be a right_incomplete for our next grid:
Choice 3, place a 2 * 1 tile, so there will be an up_incomplete for the grid next row with the same column:
In summary:
sol(x, y, right_incomplete, up_incompletes) =
max(all_possible_solutions) + take_x_y?array[x][y]:0
And by this way, we can achieve an O(n*k*2^k)
solution.
You can check my code for more details:
MAX_ANS = 10**100
def sol(matrix):
mem = {}
def _sol(x, y, up_incomplete, right_incomplete):
p = (x, y, up_incomplete, right_incomplete)
if up_incomplete[-1] and right_incomplete:
return -MAX_ANS
if x == 0 and y == 0:
if up_incomplete[-1] or right_incomplete:
return matrix[x][y]
else:
return 0
if mem.get(p) is not None:
return mem[p]
ans = 0
if y != 0:
next_x, next_y = x, y - 1
else:
next_x, next_y = x - 1, len(matrix[0]) - 1
if right_incomplete:
new_up_incomplete = tuple([False]) + up_incomplete[:-1]
ans = max(ans, matrix[x][y] + _sol(next_x, next_y, new_up_incomplete, False))
elif up_incomplete[-1]:
new_up_incomplete = tuple([False]) + up_incomplete[:-1]
ans = max(ans, matrix[x][y] + _sol(next_x, next_y, new_up_incomplete, False))
else:
if y != 0:
new_up_incomplete = tuple([False]) + up_incomplete[:-1]
ans = max(ans, matrix[x][y] + _sol(next_x, next_y, new_up_incomplete, True))
if x != 0:
new_up_incomplete = tuple([True]) + up_incomplete[:-1]
ans = max(ans, matrix[x][y] + _sol(next_x, next_y, new_up_incomplete, False))
new_up_incomplete = tuple([False]) + up_incomplete[:-1]
ans = max(ans, _sol(next_x, next_y, new_up_incomplete, False))
mem[p] = ans
return ans
return _sol(len(matrix) - 1, len(matrix[0]) - 1, tuple([False]*len(matrix[0])), False)
test_1 = [
[1, 2, 3]
, [4, -5, -6]
]
test_2 = [
[2, 6, 3, 1]
, [6, 5, 6, 1]
, [2, -6, 2, 1]
]
test_3 = [
[10, -5]
, [-5, 2]
]
print(sol(test_1))
print(sol(test_2))
print(sol(test_3))