Given an array of size N*N (1<=N<=1000) . We can select only one element from each row. Once an element is selected from a given row the column containing that element is freezed. Now for further rows we can't select any element from that column. The problem is to minimize the sum of selected elements .
I am thinking of some dp approach but size of N seems a bit large. Please suggest any other way to solve this problem. Thanks.
I think the fastest way is O(N^3) using the Hungarian Algorithm unless the array has some other special property