23 lines
545 B
Rust
23 lines
545 B
Rust
|
use std::cmp::max;
|
||
|
|
|
||
|
|
impl Solution {
|
||
|
|
pub fn predict_the_winner(nums: Vec<i32>) -> bool {
|
||
|
|
let mut dp = vec![vec![0; nums.len()]; nums.len()];
|
||
|
|
|
||
|
|
// initialize
|
||
|
|
for (i, &num) in nums.iter().enumerate() {
|
||
|
|
dp[i][i] = num;
|
||
|
|
}
|
||
|
|
|
||
|
|
// carry on the DP
|
||
|
|
for d in 1..nums.len() {
|
||
|
|
for l in 0..nums.len() - d {
|
||
|
|
let r = l + d;
|
||
|
|
dp[l][r] = max(nums[l] - dp[l + 1][r], nums[r] - dp[l][r - 1]);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
dp[0][nums.len() - 1] >= 0
|
||
|
|
}
|
||
|
|
}
|