4ms dp solution
\n\n# Intuition\nSort the cells according to there value. Then for each value segments, update the dp array according to the result of previous segment to ensur
![image.png](https://assets.leetcode.com/users/images/e25c0d36-07d1-44bd-9254-46c389550c0f_1725417266.9803193.png)\n\n# Intuition\nSort the cells according to there value. Then for each value segments, update the dp array according to the result of previous segment to ensure the selected number not duplicate.\n\n# Complexity\n- Time complexity:\n$$O(m\\times n\\times 2^m)$$\n\n- Space complexity:\n$$O(2^m)$$\n\n# Code\n```rust []\nuse std::cmp::Ordering;\n\n#[derive(Debug, Eq, PartialEq, Clone)]\nstruct Cell{\n    loc: (usize, usize),\n    val: i32\n}\n\nimpl Ord for Cell{\n    fn cmp(&self, other: &Self)->Ordering{\n        other.val.cmp(&self.val).then(self.loc.cmp(&other.loc))\n    }\n}\n\nimpl PartialOrd for Cell{\n    fn partial_cmp(&self, other: &Self)->Option<Ordering>{\n        Some(self.cmp(other))\n    }\n}\n\nimpl Solution {\n    pub fn max_score(grid: Vec<Vec<i32>>) -> i32 {\n        let (m, n) = (grid.len(), grid[0].len());\n        let mut cells=Vec::new();\n        for i in 0..m{\n            for j in 0..n{\n                cells.push(Cell{loc: (i, j), val: grid[i][j]});\n            }\n        }\n        cells.sort_unstable();\n        \n        let mut i=0;\n        let mut dp=vec![0; 1<<m];\n        while i<cells.len(){\n            let mut j=i;\n            while j<cells.len()&&cells[i].val==cells[j].val{j+=1;}\n            let mut tmp=dp.clone();\n            for k in i..j{\n                let c=&cells[k];\n                for m in 0..dp.len(){\n                    if m&1<<c.loc.0!=0{continue;}\n                    tmp[m|1<<c.loc.0]=tmp[m|1<<c.loc.0].max(dp[m]+c.val);\n                }\n            }\n\n            dp=tmp;\n            i=j;\n        }\n        dp[dp.len()-1]\n    }\n}\n```
['Array', 'Dynamic Programming', 'Bit Manipulation', 'Matrix', 'Bitmask', 'Rust']