Trying to be Beginner-Friendly
Intuition\n Describe your first thoughts on how to solve this problem. \nCould be done with normal recursion where the constraint look like normal recursion wou
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nCould be done with normal recursion where the constraint look like normal recursion would work. If you solve with normal recursion you are going to get a TLE, which would make you think "Oh, we just need a dp" and take the changing parameter as just i, it would be wrong. As we are have a condition where all the values have to unique. For that, we might have considered a set to have a track of all the unique values.\n\n```java [] \nclass Solution {\n    int rec(int i,List<List<Integer>> grid,Set<Integer> set,int[] dp){\n        if(i>=grid.size()){\n            return 0;\n        }\n        int max = 0;\n        if(dp[i]!=-1) return dp[i];\n        int k;\n        for( k = 0;k<grid.get(0).size();k++){\n\n            // System.out.println(set);\n            // System.out.println(grid.get(i).get(k));\n            \n            if(!set.contains(grid.get(i).get(k))){\n                set.add(grid.get(i).get(k));\n                max = Math.max(grid.get(i).get(k)+rec(i+1,grid,set,dp),max);\n                set.remove(grid.get(i).get(k));\n            }\n\n        }  \n        max = Math.max(rec(i+1,grid,set,dp),max); \n        return max;\n    }\n    public int maxScore(List<List<Integer>> grid) {\n        Set<Integer> set = new HashSet<>();\n        int[][] dp = new int[grid.size()][grid.get(0).size()];\n        for(int[] d:dp){\n            Arrays.fill(d,-1);\n        }\n        int max = 0;\n        max = Math.max(max,rec(0,grid,set,dp[0]));\n        return max;\n    }\n}\n```\n\nHow could something like a set be stored in dp?\nA: DP with BitMask\n\nwhat would the bitmask have?\nA: I would like to share this for first understanding why bitmask is used, how it is used in implementation\nhttps://www.reddit.com/r/leetcode/comments/11pr0co/i_finally_got_around_to_learning_bitmask_dp/\n\n```java [Starter Code for Campus bikes in the reddit post]\nimport java.util.*;\n\npublic class Solution {\n    \n    // Method to find the minimum sum of Manhattan distances\n    public int assignBikes(int[][] workers, int[][] bikes) {\n        // Your logic to find the minimum sum of Manhattan distances goes here\n        return 0;\n    }\n\n    // Main method to test the solution\n    public static void main(String[] args) {\n        Solution solution = new Solution();\n\n        // Example 1\n        int[][] workers1 = {{0, 0}, {2, 1}};\n        int[][] bikes1 = {{1, 2}, {3, 3}};\n        System.out.println("Output: " + solution.assignBikes(workers1, bikes1));  // Expected Output: 6\n\n        // Example 2\n        int[][] workers2 = {{0, 0}, {1, 1}, {2, 0}};\n        int[][] bikes2 = {{1, 0}, {2, 2}, {2, 1}};\n        System.out.println("Output: " + solution.assignBikes(workers2, bikes2));  // Expected Output: 4\n\n        // Example 3\n        int[][] workers3 = {\n            {0, 0}, {2, 1}, {4, 2}, {6, 3}, {8, 4}, {10, 5}, {12, 6}, {14, 7}, {16, 8}, {18, 9}\n        };\n        int[][] bikes3 = {\n            {9, 9}, {7, 6}, {5, 3}, {3, 2}, {1, 1}, {11, 10}, {13, 12}, {15, 14}, {17, 16}, {19, 18}\n        };\n        System.out.println("Output: " + solution.assignBikes(workers3, bikes3));\n        // The expected output will depend on your algorithm, but this case is designed to stress-test your logic and efficiency.\n\n    }\n\n}\n```\nAfter you were able to solve the problem campus bikes on your own and were able to apply dp, you would easily understand why bitmask is used (which is generally used to replicate the visited arr)\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThen i had issues on how this understanding could be applied to this problem because, i was thinking how would the visited arr concept could be applied to this problem.\n\nSo, to get this understanding for this problem i saw other solution for this problem which not so easy to get at the first go\nhttps://leetcode.com/problems/select-cells-in-grid-with-maximum-score/solutions/5718459/simple-solution-using-memo-bitmasking\n\nSo simply what he is doing, (rather just see his video and relate)\n-\n1. As there was no visited arr when we had taken the approach of normal recursion, here assume the visited arr for the rows and use a bitmask for the marking what row is visited (which wouldn\'t make sense when we are coming from that set recursion approach)\n2. Instead of set for uniqueness, we use a map, where the map stores the value in the arr and the index of the row\n3. But before this have all unique values in a list sort in descending order, according to the video, if you want to get maximum output, it is better to consider the maximum values in each row so rather than going through the each row every time, we would just have the values and their corresponding indices in the map.\n4. Now you have the list which is sorted in the descending order instead of passing the grid you could simply pass list that we have created, and then iterate through it considering all the values that it was present in the grid\n5. As you take the values you just mark the row as marked with the help of bitmask as there are only 10 rows\n\nSo now jth index of the values is eliminated\n\nTime Complexity: $$O(2N\u2217N)$$\n\n# Code\n```java []\nclass Solution {\n    int rec(int i,List<Integer> l,HashMap<Integer,Set<Integer>> map,int bitmask,int[][] dp){\n        if(i>=l.size()){\n            return 0;\n        }\n        int max = 0;\n        if(dp[i][bitmask]!=-1) return dp[i][bitmask];\n        // System.out.println(l.get(i));\n        for(int k: map.get(l.get(i))){\n            if((bitmask&(1<<k))==0){\n                max = Math.max(l.get(i)+rec(i+1,l,map,bitmask|(1<<k),dp),max);\n            }\n\n        }  \n        max = Math.max(rec(i+1,l,map,bitmask,dp),max); \n        return dp[i][bitmask] =  max;\n    }\n    public int maxScore(List<List<Integer>> grid) {\n        Set<Integer> set = new HashSet<>();\n\n        for(var g:grid){\n            for(var v:g){\n                set.add(v);\n            }\n        }\n        List<Integer> l = new ArrayList<>();\n        for(var i:set){\n            l.add(i);\n        }\n        Collections.sort(l,(a,b)->{\n            return b-a;\n        });\n        int[][] dp = new int[l.size()][1<<11];\n\n        for(int[] d:dp){\n            Arrays.fill(d,-1);\n        }\n        // for(var g:grid){\n        //     Collections.sort(g,(a,b)->{\n        //         return b-a;\n        //     });\n        // }\n\n        HashMap<Integer,Set<Integer>> map = new HashMap<>();\n        for(int i =0;i<grid.size();i++){\n            for(int j =0;j<grid.get(0).size();j++){\n                if(!map.containsKey(grid.get(i).get(j))){\n                    map.put(grid.get(i).get(j),new HashSet<Integer>());\n                }\n                map.get(grid.get(i).get(j)).add(i);\n            }\n        }\n        // System.out.println(grid);\n        // System.out.println(map);\n        // System.out.println(set);\n        // System.out.println(l);\n        // System.out.println();\n        int max = 0;\n        // for(int i = 0;i<grid.size();i++)\n            max = Math.max(max,rec(0,l,map,0,dp));\n        return max;\n    }\n}\n```
['Dynamic Programming', 'Bitmask', 'Java']