(JAVA) Top-down DP WITHOUT bitmasking
Intuition\nI am doing it just for fun. It is exactly the same except that we are using a string to represent all the rows from which we have already selected a 
# Intuition\nI am doing it just for fun. It is exactly the same except that we are using a string to represent all the rows from which we have already selected a cell so far.\n\n# Approach\nNotice that this problem has overlapping sub-problems and optimal sub-structure so we can try recursion with memo. \n\n# Complexity\n- Time complexity:\n$$O(m * n*log(m * n) + m * n * 2 ^ m)$$\n\n- Space complexity:\n$$O(2^m)$$\n\n# Code\n```java []\nimport java.util.*;\n\nclass Solution {\n    Map<String, Integer> cache;\n\n    public int maxScore(List<List<Integer>> grid) {\n        int m = grid.size();\n        int n = grid.get(0).size();\n        Map<Integer, List<Integer>> map = new HashMap<>();\n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                int val = grid.get(i).get(j);\n                map.putIfAbsent(val, new ArrayList<>());\n                map.get(val).add(i);\n            }\n        }\n        List<Integer> arr = new ArrayList<>(map.keySet());\n        Collections.sort(arr, (a, b) -> b - a); // Sort values in grid in non-increasing order\n        cache = new HashMap<>();\n        boolean[] used = new boolean[m]; // Check if a cell in this row has been selected\n        return helper(map, arr, 0, used);\n    }\n\n    private int helper(Map<Integer, List<Integer>> map, List<Integer> arr, int index, boolean[] used) {\n        if (index == arr.size()) {\n            return 0;\n        }\n        String key = index + ":" + Arrays.toString(used);\n        if (cache.containsKey(key)) {\n            return cache.get(key);\n        }\n        int max = helper(map, arr, index + 1, used); // Just skip\n        int val = arr.get(index);\n        for (int row : map.get(val)) {\n            if (!used[row]) { // No chosen from this row yet\n                used[row] = true;\n                max = Math.max(max, val + helper(map, arr, index + 1, used));\n                used[row] = false;\n            }\n        }\n        cache.put(key, max);\n        return max;\n    }\n}\n\n\n```
['Java']