solve_leetcode/problems/
0877-stone-game.rs

1/// `f(i, j)` represents:
2/// when starting with `piles[i..=j]`,
3/// the one who starts first will get `f(i, j)` more than the other one.
4///
5/// Note that `0 ≤ i ≤ j < piles.len()` and `f(i, j)` might be negative.
6///
7/// If `i == j`, `f(i, j) = piles[i]`
8///
9/// Else,
10///
11/// ```ignore
12/// f(i, j) = max(
13///     // the player takes piles[i]
14///     piles[i] - f(i + 1, j),
15///     // the player takes piles[j]
16///     piles[j] - f(i, j - 1),
17/// )
18/// ```
19///
20/// The one who starts first will win the game if and only if `f(0, n-1) > 0`
21///
22/// Now the problem is to get `f(0, n-1)`
23pub mod dp {
24    use std::cmp::max;
25
26    pub fn solve(piles: &[i32]) -> bool {
27        let n = piles.len();
28        let mut dp = vec![-1; n * n];
29        for i in (0..n).rev() {
30            for j in i..n {
31                if i == j {
32                    dp[i * n + j] = piles[i];
33                } else {
34                    let f1 = dp[(i + 1) * n + j];
35                    let f2 = dp[i * n + j - 1];
36                    assert_ne!(f1, -1);
37                    assert_ne!(f2, -1);
38                    dp[i * n + j] = max(piles[i] - f1, piles[j] - f2);
39                }
40            }
41        }
42
43        dp[n - 1] > 0
44    }
45}
46
47#[cfg(test)]
48mod tests {
49    #[test]
50    fn problem_0877() {
51        for solve in [
52            //
53            super::dp::solve,
54        ] {
55            for (piles, result) in [
56                //
57                (&[1][..], true),
58                (&[1, 4], true),
59                (&[5, 3, 4, 5], true),
60                (&[3, 7, 2, 3], true),
61                (&[1, 3, 1], false),
62            ] {
63                let solved = solve(piles);
64
65                assert_eq!(solved, result);
66            }
67        }
68    }
69}
solve_leetcode/problems/0877-stone-game.rs

solve_leetcode/problems/
0877-stone-game.rs
