CODEWITHSUNDEEP
matrixdynamic-programming
someone12321
someone12321

Reputation: 755

Using dynamic programming to find minimal sum in matrix

I need to implement this in my program, let's say we have given matrix with size N*M where N<=100 and M<=15

Now we have to find the minimal sum such that we should pick exactly one element from each column and we cannot pick two elements form different column that are in same row

For example, let N = 3 , M =2 we have the matrix

[3, 0],

[6, 9],

[5, 9],

We can choose 3+9, 6+0, 6+9, 5+0, 5+9, but not 3+0.

I know that i can solve with recursion in N^M time complexity but i need faster solution, please give me some hints.

Upvotes: 1

Views: 269

Answers (1)

DAle
DAle

Reputation: 9117

Let's iterate through all rows from 1 to N. Our dynamic programming state will be the pair (i, j), where i is a row number, j - bit mask of already used columns (columns will be zero-based in mask). We will find the values of function F(i, j) - minimal sum, that can be achieved using first i rows and taking elements from columns encoded in j. The answer will be the value of F(N, (1<<M) - 1). The recurrence:

F(0, 0) = 0
F(0, i) = MAXN, where i > 0        
F(i, j) = min(F(i-1, j), F(i-1, j ^ (1<<k)) + Matrix[i][k+1]), where 0<=k<M, j & (1<<k) != 0

Upvotes: 1

Related Questions