Easy Video Solution 🔥 || How to 🤔 in Interview || Focus on uniqueness || Memo + Bitmasking 🥲
If you like the solution Please Upvote and subscribe to my youtube channel\n\n# Intuition\n Describe your first thoughts on how to solve this problem. \nTry to 
***If you like the solution Please Upvote and subscribe to my youtube channel***\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTry to think in terms of values, Ascending or Desending\n\n\n\n***Easy Video Explanation with Proofs***\n\nhttps://youtu.be/lvUte5NcTJ4\n    \n\n# Code\n\n\n```C++ []\nclass Solution {\npublic:\n    int dp[2001][101];\n    int solve(int i,int n,vector<int>&t,map<int,vector<int>>&mp,int mask) {\n        if(i==n)\n            return 0;\n        if(dp[mask][i]!=-1)\n            return dp[mask][i];\n        int ans=0;\n        for(auto j:mp[t[i]]) {\n            if((mask&(1<<j))==0) {\n                ans=max(ans,t[i]+solve(i+1,n,t,mp,(mask|(1<<j))));\n            }\n        }\n        ans=max(ans,solve(i+1,n,t,mp,mask));\n        return dp[mask][i]=ans;\n    }\n    int maxScore(vector<vector<int>>& v) {\n        int n = v.size();\n        int m = v[0].size();\n        set<int>s;\n        for(int i=0;i<n;i++) {\n            for(int j=0;j<m;j++) {\n                s.insert(v[i][j]);\n            }\n        }\n        vector<int>t;\n        for(auto i:s)\n            t.push_back(i);\n        sort(t.begin(),t.begin(),greater<int>());\n        map<int,vector<int>>mp;\n        for(int i=0;i<n;i++) {\n            for(int j=0;j<m;j++) {\n                mp[v[i][j]].push_back(i);\n            }\n        }\n        memset(dp,-1,sizeof(dp));\n        return solve(0,t.size(),t,mp,0);\n    }\n};\n```\n```python []\nfrom typing import List\nfrom collections import defaultdict\nimport functools\n\nclass Solution:\n    def __init__(self):\n        self.dp = [[-1] * 101 for _ in range(2001)]\n\n    @functools.lru_cache(None)\n    def solve(self, i: int, n: int, t: tuple, mp: dict, mask: int) -> int:\n        if i == n:\n            return 0\n        if self.dp[mask][i] != -1:\n            return self.dp[mask][i]\n\n        ans = 0\n        for j in mp[t[i]]:\n            if not (mask & (1 << j)):\n                ans = max(ans, t[i] + self.solve(i + 1, n, t, mp, mask | (1 << j)))\n        ans = max(ans, self.solve(i + 1, n, t, mp, mask))\n        self.dp[mask][i] = ans\n        return ans\n\n    def maxScore(self, v: List[List[int]]) -> int:\n        n = len(v)\n        m = len(v[0])\n        s = set()\n\n        for i in range(n):\n            for j in range(m):\n                s.add(v[i][j])\n\n        t = sorted(s, reverse=True)\n\n        mp = defaultdict(list)\n        for i in range(n):\n            for j in range(m):\n                mp[v[i][j]].append(i)\n\n        self.dp = [[-1] * 101 for _ in range(2001)]\n        return self.solve(0, len(t), tuple(t), mp, 0)\n\n```\n```Java []\nimport java.util.*;\n\nclass Solution {\n    int[][] dp = new int[2001][101];\n\n    int solve(int i, int n, List<Integer> t, Map<Integer, List<Integer>> mp, int mask) {\n        if (i == n) return 0;\n        if (dp[mask][i] != -1) return dp[mask][i];\n\n        int ans = 0;\n        for (int j : mp.get(t.get(i))) {\n            if ((mask & (1 << j)) == 0) {\n                ans = Math.max(ans, t.get(i) + solve(i + 1, n, t, mp, (mask | (1 << j))));\n            }\n        }\n        ans = Math.max(ans, solve(i + 1, n, t, mp, mask));\n        return dp[mask][i] = ans;\n    }\n\n    public int maxScore(List<List<Integer>> v) {\n        int n = v.size();\n        int m = v.get(0).size();\n        Set<Integer> s = new HashSet<>();\n\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < m; j++) {\n                s.add(v.get(i).get(j));\n            }\n        }\n\n        List<Integer> t = new ArrayList<>(s);\n        Collections.sort(t, Collections.reverseOrder());\n\n        Map<Integer, List<Integer>> mp = new HashMap<>();\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < m; j++) {\n                mp.computeIfAbsent(v.get(i).get(j), k -> new ArrayList<>()).add(i);\n            }\n        }\n\n        for (int[] row : dp) {\n            Arrays.fill(row, -1);\n        }\n\n        return solve(0, t.size(), t, mp, 0);\n    }\n}\n\n\n```\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n    O(2^10*1000*10)\n    \n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n    O(N)\n\n# ***If you like the solution Please Upvote and subscribe to my youtube channel***\n***It Motivates me to record more videos***\n\n*Thank you* \uD83D\uDE00
['Memoization', 'Bitmask', 'C++', 'Java', 'Python3']