1
impl Solution {
2
  pub fn predict_the_winner(nums: Vec<i32>) -> bool {
3
    fn dfs(l: usize, r: usize, nums: &Vec<i32>, table: &mut Vec<Vec<i32>>) -> i32 {
4
      if table[l][r] != -1 {
5
        return table[l][r];
6
      }
7
      if l == r {
8
        return nums[l];
9
      }
10
      let left = nums[l] - dfs(l + 1, r, nums, table);
11
      let right = nums[r] - dfs(l, r - 1, nums, table);
12
      table[l][r] = left.max(right);
13
      table[l][r]
14
    }
15

16
    let n = nums.len();
17
    let mut table = vec![vec![-1; n]; n];
18
    dfs(0, n - 1, &nums, &mut table) >= 0
19
  }
20
}