I have a problem where I have a N x 3 matrix with int values. I need to tile it with K 2x1 or 1x2 tiles so that they do not overlap and that I get the maximum sum with the use of dynamic programming. What would the best way be to solve such a problem?
Example 5 x 3 matrix, K = 5:
2 6 2
6 5 6
2 6 2
1 1 1
1 1 1
Good tiles: (6,2), (6,2), (6,2), (6,5), (2,1)
Result = 38
And an example with an edge case:
2 x 3 Matrix, K = 2
0 4 1
3 4 1
Good tiles: (4,1), (4,3)
Result = 12
Let's define the state of a row as the cells that are covered by some of the K bricks. You have 8 combinations (2^3) from 000 (everything is not covered) to 111 (everything is covered) (you can use binary to encode the state for efficiency).
The dynamic programming matrix will be a[row][tiles][state]. Where row is the row we are processing, going top to bottom, tiles is how many tiles you placed already, state is the state as we defined above and the value is the current maximum sum.
To fill it we go top to bottom. We simplify things by only allowing a vertical tile to be placed on the current and the row above (not below). You can iterate through tile placement combinations between the rows (some are mutually exclusive). You have 3 vertical options and 2 horizontal options on the current row (5 options, for a total of 12 combinations, if I've done the math right). Also iterate through the possible values of 'titles'. For each combination look for all possible combination that allow it's placement on the previous row (so that the vertical tiles don't overlap) take the maximum and update the dynamic matrix. Some combinations are very strict (3 vertical tiles require 000 in the row above), while some are very relaxed (1 horizontal tile allows for every posibility). Do this on paper a few times to see how it works.
As an optimization note that you only need to know the values from the previous row, as the ones above that don't factor into so you can keep only the previous row and current row.
Algorithm should look something like this
For i from 0 to N
for tiles from 0 to K
for each combination
if tiles - combination.tiles < 0: continue
m = -1
for each state compatible with combination.previous_row
m = max(m, a[i-1][tiles - combination.tiles][state])
if m > 0
a[i][tiles][combination.state] = max(a[i][tiles][combination.state], m)
The solution is the maximum between the states on last row with tiles=K.
Complexity will be N*K* 12 combinations * 2^3 states so O(N*K). Memory can be O(K) with the trick I've mentioned above.