DP Bitmask
Intuition\n Describe your first thoughts on how to solve this problem. \nWe are going to convert this 2d array into a 1d and write a dp solutions , this convert
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe are going to convert this 2d array into a 1d and write a dp solutions , this convertion makes the array sorted and unique values will be clubed \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nDP bitmask \nLet us take an example : \n[[3,4],[4,1]] \n\nconvertion : \nwe will add row to the number and sorted \n\n[[3,0].[4,0],[4,1],[1,1]] (3,4,4,1 are number , 0,0,1,1 are rows)\n\nsorted : [[1,1],[3,0],[4,0],[4,1]] ;\n\nNow it is similarly to 0-1 knapsack\n\nI have written the top down approach here \n\nBasically we can or we will not , if we chose to take an index i and next index j value should be equal that is nextidx function helper is the dp function and add memo here , Used bitmask to know which values of rows are taken \n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n * (2^n)) n--> length of grid \n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n * (2^n))\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int n ,m ;\n    vector <vector <int>> dp ;\n    int nextidx(vector <pair<int,int>>&arr,int i){\n        for(int j=i-1;j>=0;j--){\n            if(arr[j].first!=arr[i].first)return j ;\n        }\n        return -1 ;\n    }\n    int helper(vector <pair<int,int>>&arr,int i,int mask){\n        if(i<0)return 0 ;\n        if(dp[i][mask]!=-1)return dp[i][mask] ;\n        int num = arr[i].first , row = arr[i].second ;\n        int tempmask = 1 << row ;\n        int ans1 = helper(arr,i-1,mask) ;\n        if(tempmask & mask )return dp[i][mask]=ans1 ;\n        \n        int j = nextidx(arr,i) ;\n        \n        int mask1 = mask | tempmask ;\n        int ans2 = num+helper(arr,j,mask1) ;\n        return dp[i][mask]=max(ans1,ans2) ;\n        \n        \n    }\n    int maxScore(vector<vector<int>>& grid) {\n        dp.resize(101,vector <int> (1025,-1)) ;\n        vector <pair<int,int>> arr ;\n        n=grid.size(),m=grid[0].size();\n        for(int i=0;i<n;i++){\n            for(int j=0;j<m;j++){\n                arr.push_back({grid[i][j],i}) ;\n            }\n        }\n        \n        sort(arr.begin(),arr.end()) ;\n        int sz = n*m ;\n        return helper(arr,sz-1,0) ;\n    }\n};\n```
['C++']