dp solution
Intuition\nThis is an overly complex question. The question can be simplify as below:\n\nGiving severly cards with one master card. Each time choose a non-maste
# Intuition\nThis is an overly complex question. The question can be simplify as below:\n\n**Giving severly cards with one master card. Each time choose a non-master card and let the master take its place with some fix cost. Whether to maximize of minimize the cost change alternately**\n\nThe cost only depend on the index of these cards. In this case, pre-calculate it within chase rules.\n\nJust use dp. the status is which card is the master, and which non-master cards are left. Use bitmask to represent the second.\n\nSince you can count how many non-master cards left, you don\'t need to record the player in the status;\n\n# Complexity\n- Time complexity:\n$$O(n(n+1)*2^n)$$\n\n- Space complexity:\n$$O((n+1)*2^n)$$\n\n# Code\n```rust []\nimpl Solution {\n    pub fn max_moves(kx: i32, ky: i32, positions: Vec<Vec<i32>>) -> i32 {\n        let pos:Vec<_>=positions.iter().map(|p|(p[0], p[1])).chain(std::iter::once((kx, ky))).collect();\n        let n=pos.len()-1;\n\n        let d=[(1, 2), (-1, 2), (1, -2), (-1, -2), (2, 1), (-2, 1), (2, -1), (-2, -1)];\n        let mut s=Vec::new();\n        for i in 0..pos.len()-1{\n            let mut cur=vec![0; pos.len()-i-1];\n            let mut left=cur.len();\n            let mut prev=vec![pos[i]];\n            let mut seen=vec![vec![false; 50]; 50];\n            seen[pos[i].0 as usize][pos[i].1 as usize]=true;\n            let mut step=0;\n            while left>0{\n                let mut nxt=Vec::new();\n                for &p in &prev{\n                    for j in i+1..pos.len(){\n                        if pos[j]==p{\n                            cur[j-1-i]=step;\n                            left-=1;\n                            break;\n                        }\n                    }\n                    for &dr in &d{\n                        let (nx, ny)=(p.0+dr.0, p.1+dr.1);\n                        if nx>=0&&nx<50&&ny>=0&&ny<50&&!seen[nx as usize][ny as usize]{\n                            nxt.push((nx, ny));\n                            seen[nx as usize][ny as usize]=true;\n                        }\n                    }\n                }\n                step+=1;\n                prev=nxt;\n            }\n            s.push(cur);\n        }\n        \n        let mut dp=vec![-1; (n+1)*(1<<n)];\n        for i in 0..n{\n            dp[i*(1<<n)]=0;\n        }\n        Self::dp((n+1)*(1<<n)-1, n, true, &mut dp, &s)\n    }\n\n    fn dp(mark: usize, n: usize, is_alice: bool, dp: &mut Vec<i32>, s: &Vec<Vec<i32>>)->i32{\n        if dp[mark]<0{\n            let (mask, cur)=(mark%(1<<n), mark/(1<<n));\n            dp[mark]=if is_alice{\n                (0..n).filter(|i|mask&(1<<i)!=0)\n                .map(|i|{\n                    let (a, b)=(i.min(cur), i.max(cur));\n                    Self::dp(i*(1<<n)+(mask-(1<<i)), n, !is_alice, dp, s)+s[a][b-a-1]})\n                .max().unwrap()\n            }else{\n                (0..n).filter(|i|mask&(1<<i)!=0)\n                .map(|i|{\n                    let (a, b)=(i.min(cur), i.max(cur));\n                    Self::dp(i*(1<<n)+(mask-(1<<i)), n, !is_alice, dp, s)+s[a][b-a-1]})\n                .min().unwrap()\n            };\n        }\n        dp[mark]\n    }\n}\n```
['Array', 'Dynamic Programming', 'Bitmask', 'Rust']