Dynamic Programming with Bitmask Optimization
\n\n# Approach\n Describe your approach to solving the problem. \n1. Value Grouping:\n   - Create a Map (vals) where each key is a unique value from the grid, a
\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Value Grouping**:\n   - Create a `Map` (`vals`) where each key is a unique value from the grid, and the value is an array of row indices where this value appears.\n   - Ensures each unique value is considered only once.\n\n2. **Sorting**:\n   - Convert the `Map` to an array of `[value, row_indices]` pairs and sort in descending order of values.\n   - Prioritizes higher values for a potentially higher sum.\n\n3. **Dynamic Programming with Bitmask**:\n   - Use a recursive function `maxval` with memoization to explore combinations.\n   - Parameters:\n     - `i`: Index of the current value in the sorted array.\n     - `mask`: Bitmask representing used rows (1 if used, 0 if not).\n   - Options for each value:\n     - Skip it and move to the next.\n     - Include it if from an unused row, then move to the next.\n   - Use memoization (`memo`) to avoid redundant calculations.\n\n4. **Maximization**:\n   - At each step, choose the maximum between skipping and including the current value.\n   - Ensures the best possible sum is always considered.\n# Complexity\n- Time complexity: O(n 2^n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n 2^n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```typescript []\nfunction maxScore(grid: number[][]): number {\n    const n: number = grid.length;\n    const vals: Map<number, number[]> = new Map();\n    \n    // Collect the values and their row indices\n    for (let i = 0; i < n; i++) {\n        for (let h of grid[i]) {\n            if (!vals.has(h)) {\n                vals.set(h, []);\n            }\n            vals.get(h)!.push(i);\n        }\n    }\n    \n    // Convert the Map to a sorted array\n    const valsArray: [number, number[]][] = Array.from(vals.entries()).sort((a, b) => b[0] - a[0]);\n    \n    // Create a memoization cache\n    const memo: Map<string, number> = new Map();\n    \n    // Define the recursive function with memoization\n    const maxval = (i: number, mask: number): number => {\n        if (i >= valsArray.length) {\n            return 0;\n        }\n        const key: string = `${i}-${mask}`;\n        if (memo.has(key)) {\n            return memo.get(key)!;\n        }\n        \n        // Option 1: Skip current value\n        let res: number = maxval(i + 1, mask);\n        \n        // Option 2: Include current value if the row is not used\n        for (let j of valsArray[i][1]) {\n            if (!(mask & (1 << j))) {\n                res = Math.max(res, valsArray[i][0] + maxval(i + 1, mask | (1 << j)));\n            }\n        }\n        \n        memo.set(key, res);\n        return res;\n    };\n    \n    return maxval(0, 0);\n};\n```
['Dynamic Programming', 'Greedy', 'Memoization', 'Bitmask', 'TypeScript']