1
impl Solution {
2
  pub fn stone_game_ii(piles: Vec<i32>) -> i32 {
3
    let mut cache = vec![vec![None; piles.len() + 1]; piles.len() + 1];
4
    GameState::new(&mut cache, &piles).best_outcome().0
5
  }
6
}
7

8
struct GameState<'a> {
9
  cache: &'a mut Vec<Vec<Option<(i32, i32)>>>,
10
  piles: &'a [i32],
11
  m: usize,
12
}
13

14
impl<'a, 'b> GameState<'a> {
15
  fn new(cache: &'a mut Vec<Vec<Option<(i32, i32)>>>, piles: &'a [i32]) -> Self {
16
    Self { cache, piles, m: 1 }
17
  }
18

19
  fn next_state(&'b mut self, x: usize) -> GameState<'b> {
20
    GameState {
21
      cache: &mut self.cache,
22
      piles: &self.piles[x..],
23
      m: self.m.max(x),
24
    }
25
  }
26

27
  fn best_outcome(mut self) -> (i32, i32) {
28
    let n = self.piles.len();
29
    let maybe_cached_outcome = self
30
      .cache
31
      .get(n)
32
      .and_then(|row| row.get(self.m.min(n)))
33
      .and_then(|&outcome| outcome);
34

35
    if let Some(outcome) = maybe_cached_outcome {
36
      return outcome;
37
    }
38

39
    let max_x = n.min(2 * self.m);
40

41
    let mut taken = 0;
42
    let mut best_outcome = (0, 0);
43
    for x in (1..=max_x) {
44
      taken += self.piles[x - 1];
45
      let future_outcome = self.next_state(x).best_outcome();
46
      if taken + future_outcome.1 > best_outcome.0 {
47
        best_outcome = (taken + future_outcome.1, future_outcome.0);
48
      }
49
    }
50
    self.cache[n][self.m.min(n)] = Some(best_outcome);
51
    best_outcome
52
  }
53
}