Focus on uniqueness in values first, then uniqueness in rows | Full explanation
So this one is a tricky one. Brute force suggests to try all possibilities on rows and maintain uniqueness through sets, which results in tle.\n\nThe optimisati
So this one is a tricky one. Brute force suggests to try all possibilities on rows and maintain uniqueness through sets, which results in tle.\n\nThe optimisation lies in the fact that we can store values in increasing/ decreasing order and then only select values greater than / less than the previous value. This ensures uniqueness.\n\nAs for row uniqueness, we can store which row has been taken in previous states through a mask variable. The total possible values of this variable is 2^ (No. of rows) which fits well in the time constraints.\n```\nclass Solution {\npublic:\n    int recur(vector<vector<int>>& values, int idx, int mask_row, map<pair<int,int>, int>& dp)\n    {\n        int n= values.size();\n        if(idx == n)\n            return 0;\n        \n        if(dp.find({idx, mask_row})!= dp.end())\n            return dp[{idx, mask_row}];\n        \n        int ans = 0;\n        int row = values[idx][1];\n        if((1<<row) & mask_row)\n            ans += recur(values, idx+1, mask_row, dp);\n        else\n        {\n            int j = idx;\n            while (j< n and values[idx][0]== values[j][0])\n                j++;\n            \n            int ans1= values[idx][0]+ recur(values, j, mask_row | (1<<row), dp);\n            int ans2 = recur(values, idx+1, mask_row, dp);\n            \n            ans= max(ans1, ans2);\n        }\n            \n        return dp[{idx, mask_row}]= ans;\n        \n    }\n    int maxScore(vector<vector<int>>& grid) {\n        int n= grid.size();\n        int m= grid[0].size();\n        vector<vector<int>> values;\n        for(int i=0; i<n; i++)\n        {\n            for(int j=0; j<m; j++)\n            {\n                values.push_back({grid[i][j], i, j});\n            }\n        }\n        \n        \n        sort(values.begin(), values.end(), greater<vector<int>>());\n        map<pair<int,int>, int> dp;\n        \n        return recur(values, 0, 0, dp);\n    }\n};\n```\n\nTC: O(M*N* 2^M) SC: O(M*N*2^(M))
['Dynamic Programming', 'Bitmask', 'C++']