What is a good way to solve the following:
In the grid below, choose one value from each row such that no column is used more than once; the sum of the choices must be maximized. Number of rows <= 1500.
A B C D
e 5 8
f 3 9 2
g 1 9 6 4
Working down the rows, notice that each row is left with two options, as the rest are removed by the choices made before.
Addendum
Using Psychologist's answer, we create dp grid with exactly the same structure as the input grid. Each entry means "after this row, what's the maximum so far with this column still available".
(1) First row is reversed
A B C D dp A B C D
e 5 8 e 8 5
f 3 9 2 f ? ? ?
g 1 9 6 4 g ? ? ? ?
(2) Each dp cell before the end of the row means the last cell in the input array's row is used.
A B C D dp A B C D
e 5 8 e 8 5
f 3 9 2 f 10 7 ? // 8(dp) + 2(a), 5(dp) + 2(a)
g 1 9 6 4 g ? ? ? ?
(3) With the dp cell at the end, we need to try taking each other cell to get the best.
A B C D dp A B C D
e 5 8 e 8 5
f 3 9 2 f 10 7 14 // 8(dp) + 3(a) vs. 5(dp) + 9(a)
g 1 9 6 4 g ? ? ? ?
(4) Finishing up
A B C D dp A B C D
e 5 8 e 8 5
f 3 9 2 f 10 7 14
g 1 9 6 4 g 14 11 18 20 // 10 + 4, 7 + 4, 14 + 4, (10+1 vs 7+9 vs 14+6)
The solution is then the best value in the bottom row. And thanks for showing me the right way.
Let dp[i][j] be maximal sum such that column x is left behind
dp[1][i] = a[1][3-i]
dp[i][j] = dp[i-1][j]+a[i][i] if i != j
Solution by Nezzar is pretty simple and correct and can be implemented in O(n2).
In fact, this problem is a special case of an assignment problem, which can be solved in O(n3) in general case using the Hungarian algorithm or just min-cost-max-flow.