Dynamic Programming with Bitmasking
Approach Breakdown\nThis problem can be approached using Dynamic Programming combined with Bitmasking. The general idea is to recursively explore the possible s
# Approach Breakdown\nThis problem can be approached using Dynamic Programming combined with Bitmasking. The general idea is to recursively explore the possible selections, using dynamic programming to store intermediate results for optimization.\n\n# Explanation of Code\n1. Initialize the Dynamic Programming Array (dp)\nThe dp array is a 2D array where dp[ind][mask] stores the maximum score obtainable by considering all values up to ind with the corresponding bitmask mask. The mask is used to keep track of the rows from which we\'ve already selected a value. Each bit in the mask represents a row (with 1 meaning a value has been selected from that row).\n\n2. Mapping the Values\nWe create a map<int, vector<int>> index_ to store which rows contain each unique value in the grid. This allows us to easily access the rows where a particular value exists. For example, if the grid contains the number 3 in rows 0 and 1, the map would store something like index_[3] = [0, 1].\n\n2. Recursive Function solve_dp\nThe recursive function solve_dp(ind, mask, index_) is the core of the solution:\n\n    1. Base Case: If ind == 0 (we\'ve considered all possible values), the function returns 0, as there are no more values to process.\n\n    2. Memoization: If dp[ind][mask] has already been computed, we return it to avoid redundant calculations.\n\n    3. Recursive Call: For each value ind, we try two things:\n\n    4. Skip the Value: We skip the current value and continue to the next one (solve_dp(ind - 1, mask, index_)).\nPick the Value: If the row corresponding to this value has not been picked yet (checked using bitmasking), we pick the value, mark the row as selected, and add the value to our score.\nUpdate DP Table: After considering all possibilities, we update dp[ind][mask] with the maximum score we could obtain.\n\n2. Filling the index_ Map\nWe traverse through the grid and populate the index_ map with the row indices corresponding to each value in the grid.\n\n2. Driver Function maxScore\nFinally, we call the recursive function solve_dp(100, 0, index_) starting from the maximum possible value (100 as per the constraint 1 <= grid[i][j] <= 100), and using the bitmask 0 (meaning no rows have been selected yet).\n# Code\n```cpp []\nclass Solution {\nprivate:\n    int dp[105][1<<10];\n    int helper(int num,int mask,map<int,vector<int>> &rowsForNumber){\n        if(num == 0) {\n            return 0;\n        }\n        if(dp[num][mask] != -1) {\n            return dp[num][mask];\n        }\n\n        int res = helper(num-1,mask,rowsForNumber);\n\n        for(int row : rowsForNumber[num]){\n            if((mask & (1 << row)) == 0){\n                res = max(res, num + helper(num-1, mask|(1<<row) , rowsForNumber));\n            }\n        }\n\n        return dp[num][mask] = res;\n    }\npublic:\n    int maxScore(vector<vector<int>>& grid) {\n        memset(dp,-1,sizeof(dp));\n\n        map<int,vector<int>> rowsForNumber;\n        int n=grid.size(),m=grid[0].size();\n        for(int i=0; i<n; i++){\n            for(int j=0; j<m; j++){\n                rowsForNumber[grid[i][j]].push_back(i);\n            }\n        }\n\n        return helper(100,0,rowsForNumber);\n    }\n};\n```\n# Code 2\n```C++ []\nclass Solution {\nprivate:\n    int dp[105][2000];\npublic:\n    int maxScore(vector<vector<int>>& grid) {\n        memset(dp,-1,sizeof(dp));\n\n        map<int,vector<int>> rowsForNumber;\n        int n=grid.size(),m=grid[0].size();\n        for(int i=0; i<n; i++){\n            for(int j=0; j<m; j++){\n                rowsForNumber[grid[i][j]].push_back(i);\n            }\n        }\n\n        for(int num = 0; num <=100; num++){\n            for(int mask=(1<<n); mask>=0; mask--){\n                if(num==0){\n                    dp[num][mask] = 0;\n                    continue;\n                }\n\n                int res = dp[num-1][mask];\n\n                for(int row : rowsForNumber[num]){\n                    if((mask & (1 << row)) == 0){\n                        res = max(res, num + dp[num-1][ mask|(1<<row) ]);\n                    }\n                }\n\n                dp[num][mask] = res;\n            }\n        }\n        return dp[100][0];\n    }\n};\n```
['Dynamic Programming', 'Bit Manipulation', 'Bitmask', 'C++']