Stone game v

Array Math Dynamic Programming Game Theory

41.6% acceptance

Feb 25, 2026

695

Alice and Bob continue their games with piles of stones. There are several stones arranged in a row, and each stone has an associated value which is an integer given in the array stoneValue. Alice and Bob take turns, with Alice starting first. On each player's turn, that player can take 1, 2, or 3 stones from the first remaining stones in the row. The score of each player is the sum of the values of the stones taken. The score of each player is 0 initially. Alice and Bob will continue taking stones one at a time (if no stones remain, they don't take any more). The goal of each player is to win, and the winner is the player with the higher score. Although they want to win, both players also want to maximize their own scores, and when a player knows that winning is not possible, they try to minimize the score of the opponent. Note: It is guaranteed that Alice always wins. Don't forget that both players always choose optimally. Wait, I misread the problem. This is actually: Alice and Bob continue their games with piles of stones. There are several stones arranged in a row, and each stone has an associated value which is an integer given in the array stoneValue. Alice and Bob take turns, with Alice starting first. Alice splits the row into two non-empty rows (i.e. left row and right row), then Bob calculates the value of each row which is the sum of stoneValue in each row. Bob throws away the row which has the maximum value, and Alice's score increases by the value of the remaining row. This continues until there is only one stone remaining. Alice's score is initially 0. Return the maximum score that Alice can obtain.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn stone_game_v(stone_value: Vec<i32>) -> i32 {
    let n = stone_value.len();
    // prefix sums
    let mut prefix = vec![0i64; n + 1];
    for i in 0..n {
      prefix[i + 1] = prefix[i] + stone_value[i] as i64;
    }
    // dp[i][j] = max score Alice can get from stoneValue[i..=j]
    let mut dp = vec![vec![0i64; n]; n];

    // fill by length
    for len in 2..=n {
      for i in 0..=(n - len) {
        let j = i + len - 1;
        for k in i..j {
          let left_sum = prefix[k + 1] - prefix[i];
          let right_sum = prefix[j + 1] - prefix[k + 1];
          let score = if left_sum < right_sum {
            left_sum + dp[i][k]
          } else if left_sum > right_sum {
            right_sum + dp[k + 1][j]
          } else {
            (left_sum + dp[i][k]).max(right_sum + dp[k + 1][j])
          };
          dp[i][j] = dp[i][j].max(score);
        }
      }
    }
    dp[0][n - 1] as i32
  }
}