DP with bitmask | C++ | Image explanation
DP with Bitmask. \n\n1. For each number, create mask of which row.\n2. Start with mask as 0 and go till all rows are considered by checking base condition.\n \n
DP with Bitmask. \n\n1. For each number, create mask of which row.\n2. Start with mask as 0 and go till all rows are considered by checking base condition.\n ```\n if(mask == (1 << n) - 1) {\n            return 0;\n        }\n```\n\n\nNow refer image for bit masking.\n\n![Screenshot 2024-09-25 094046.png](https://assets.leetcode.com/users/images/e1e21759-fc03-4aec-84aa-510ef1a1857f_1727237472.282969.png)\n\n\n  \n# Code\n```cpp []\nclass Solution {\npublic:\n    int cache[2 << 10][105];\n    int Dfs(int mask, int j, int n, vector<int>& pos_mask, set<int>& numbers) {\n        if(mask == (1 << n) - 1) {\n            return 0;\n        }\n        if(cache[mask][j] != -1) return cache[mask][j];\n\n        int ans = 0;\n        for(int i = j; i > 0; --i) {\n            if(numbers.count(i)) {\n                for(int bit = 0; bit <= 10; ++bit) {\n                    if((pos_mask[i] & (1 << bit)) && (mask & (1 << bit)) == 0) {\n                        ans = max(ans, i + Dfs(mask | (1 << bit), i - 1, n, pos_mask, numbers));\n                    }\n                }\n                \n            }\n        }\n        return cache[mask][j] = ans;\n    }\n    int maxScore(vector<vector<int>>& grid) {\n        int n = grid.size(), m = grid[0].size();\n        set<int> numbers;\n        memset(cache, -1, sizeof(cache));\n        vector<int> pos_mask(105, 0);\n        for(int i = 0; i < n; ++i) {\n            for(int j = 0; j < m; ++j) {\n                pos_mask[grid[i][j]] = pos_mask[grid[i][j]] | (1 << i);\n                numbers.insert(grid[i][j]);\n            }\n        }\n\n        return Dfs(0, 100, n, pos_mask, numbers);\n    }\n};\n```
['C++']