Best DP + Bit Masking Approach
Intuition\nThe bitmask is used to track which rows have been visited, and dp to memoize.\n\n# Approach\nPrecomputation\nI\'m first storing the row number of all
# Intuition\nThe bitmask is used to track which rows have been visited, and dp to memoize.\n\n# Approach\n**Precomputation**\nI\'m first storing the row number of all the values present in the grid.\n- val[i] - represents a vector which stores the row indices of the value i.\n\n**Recursion**\n- Function Purpose: f(num, bit_mask) computes the maximum score using values from 1 to num, with bit_mask representing the rows visited.\n- Base Case: If num == 0, return 0 since no values are left.\n- Recursive Call: Calculate the score without including any cells with value num, f(num-1, bit_mask).\n- For Loop: For each row a in val[i], if row a is not visited, update the bitmask and include this cell. The result is the maximum of including or excluding the current value.\n\n**Memoization**\n- dp[num][bit_mask], which stores the maximum score that can be achieved considering the first num values (from 1 to 100), with bit_mask representing the bitmask of visited rows.\n\n# Complexity\n- Time complexity: O(n * 2^n * 101)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(101 * 2^n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n\n    int f(int num,int bit_mask,vector<vector<int>>& grid,vector<vector<int>>& val,vector<vector<int>> &dp){\n        if(num==0) return 0;\n        if(dp[num][bit_mask]!=-1) return dp[num][bit_mask];\n        int ans=f(num-1,bit_mask,grid,val,dp);\n        for(auto it:val[num]){\n            if(!((bit_mask>>it)&1)){\n                ans=max(ans,num+f(num-1,(bit_mask|(1<<it)),grid,val,dp));\n            }\n        }\n        return dp[num][bit_mask]=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>> val(101);\n        vector<vector<int>> dp(101,vector<int>(1025,-1));\n        for(int i=0;i<n;i++) for(int j=0;j<m;j++) val[grid[i][j]].push_back(i);\n        return f(100,0,grid,val,dp);\n    }\n};\n```
['C++']