I have learn DP recently. I am practicing DP in this OJ. Now, I am stuck on this problem.
In this problem I have to find the maximum summation of cells such that any two cells don't have the same row or column.
So, I will use recursion from top of the matrix. When using recursion I got to check if that cell is available or not, i.e. that cells row and column has not previously been used. How can I do that?
N ≤ 16, so you can use bitmasks to store which columns are available. Go row by row and each time select one column among the ones available, updating DP as necessary. I'll post code if necessary.
As a side note, this problem can also be solved much faster with min-cost max-flow, though it's obviously overkill.
Sorry , I didn't understand your technique. Can you please describe your technique? I would really appreciate it?
The DP is DP[i][mask], and it stores the maximum value we can achieve when we have processed i rows and used the columns described by bitmask mask. Then when we process the next row, we choose a column j not present in bitmask mask, and check if DP[i][mask] + A[i][j] > DP[i + 1][mask + j], where A[i][j] denotes the value at row i, column j (rows and columns are numbered from 0).
How can I store the number of columns in mask?
And why did you check DP[i][mask] + A[i][j] > DP[i+1][mask+j] ?
If you've never read about bitmasks, I recommend you read about them. For example, you can try this blog -> Bitmasks for beginners.
In short, each bit represents one element. In this case, 1 for the bit j means column j has been used. And mask + j is not actually addition, it means mask with bit j set to 1, it's just easier to write it that way than writing mask + 2j.
thnx for your help,,,,
How can i solve this problem recursively without bitmask. Actually I am beginner at dp and practicing from lightoj.
You can keep a visited array, which would store which row or column have already been visited.