DP Bitmasking | Intuition Building | Full Explanation⚡⚡
\nObservation:\n    1 <= row <= 10 and 1 <= value <= 100\n    so we have to iterate over values,\n    and we can mask the rows, \n    (masking value will be a t
\n**Observation:**\n    1 <= row <= 10 and 1 <= value <= 100\n    so we have to iterate over values,\n    and we can mask the rows, \n    (masking value will be a tedious task and gives tle, as we need to take `bitset<101>`)\n\n---\n\n**Intuition:**\nfor each value from 1 to 100 we will store in which row the value occured,\nand iterate over values from 101,\nand for each value val, we will see in which rows it occured,\nif that row is not considered earlier, we will take that value and make mask[row] = 0\nalso find for the condition when the value is not occured in any row\nso `dp(value, mask) => will store the max score till value` \n\n---\n\n**Recurrence:** \n    `dp(value, mask) = dp(value - 1, mask ^ (1 << j))`,\n    where j belongs to rowsOccurence[value]\n\n---\n\n**Note:** \n    taken mask[row] = 1, if we have not considered row till now\n\n---\n\n**Complexity**\n - TC: O(m * 2^n)\n - SC: O(m * 2^n)\n\n# Code\n```cpp []\nclass Solution {\nprivate:\n    map<int, vector<int>> occur;  // {element, {rows in which element occured}}\n    int dp[105][2050];  // {idx, mask}\nprivate:\n    int solve(int idx, int mask) {\n        if(idx == 0) {\n            return 0;\n        }\n\n        if(dp[idx][mask] != -1)  return dp[idx][mask];\n\n        int mx = 0;\n        for(int row: occur[idx]) {\n            if(mask & (1 << row)) {\n                mask = mask ^ (1 << row);\n\n                int curr = idx + solve(idx - 1, mask);\n                mx = max(mx, curr);\n\n                mask = mask ^ (1 << row);\n            }\n        }\n        \n        int curr = 0 + solve(idx - 1, mask);\n        mx = max(mx, curr);\n\n        return dp[idx][mask] = mx;\n    }\npublic:\n    int maxScore(vector<vector<int>>& grid) {\n        int n = grid.size(), m = grid[0].size();\n\n        for(int row = 0; row < n; row++) {\n            for(int col = 0; col < m; col++) {\n                int ele = grid[row][col];\n                occur[ele].push_back(row);\n            }\n        }\n\n        memset(dp, -1, sizeof dp);\n\n        int mask = (1 << 11) - 1;\n        return solve(100, mask);\n    }\n};\n\n
['Dynamic Programming', 'Bit Manipulation', 'Recursion', 'Bitmask', 'C++']