Dynamic Programming for sub sum elements in a matrix

Question

Given a chess board with 4 rows and n columns. On every cell there's an integer. Given 2n discs that part of them, or all of them you can put on a different cell on the board so the total sum is maximal. The only limitation is that 2 discs can't be next to each other vertically or horizontally. How to place the best combination of discs on the board in O(n) using DP ?

Answer 1

1st, we cannot possibly use more than 2*n disk as any column could contain at maximum 2 disks.

let's say d[i][mask] - maximum amount obtained after filling columns from 1 to i with disks so that the last column is filled as mask ( mask could be 0000, 0001, 0010, 0100, 0101, 1000, 1001 or 1010 where 1 means disk was placed and 0 means it wasn't)

So d[i][mask1] = max of (d[i-1][mask2] + number obtained from applying mask1 on i-th column), where mask2 could be any mask which doensn't contradict with mask1

Edit 1: You do not need to change anything. When you are on i-th step on certain mask, it only depends on the answers for masks of i-1. And you already have all of them. You just try to update the current d[i][mask] from those which are valid. As I already said d[i][mask] - stores the maximum value which could be obtained filling columns from 1 to i, optimally, so that the last column has disks in form of this mask (doesn't matter masks before the i-th column were filled, because they won't affect next column)