10.35

Idea. Let a[0 … n-1] be the digits of the given number and sum(i,j) be the sum of digits from position i to j (inclusive). For any interval [i,j] define   dp[i][j] = best total the current player can collect from that interval if both play optimally. When the current player removes a digit he immediately gets its value; the remainder of the interval is then played by the opponent, who will in turn take dp[…] points out of it. Hence

dp[i][j] = max( a[i] + (sum(i+1,j) − dp[i+1][j]), // take left digit a[j] + (sum(i, j-1) − dp[i][j-1]) // take right digit )

Base case: dp[i][i] = a[i]. The answer for the original number is dp[0][n-1]. Pseudocode (O(n²) time, O(n²) memory; 1-D space can be used as well)

a = list of digits n = len(a) # prefix sums for O(1) range-sum queries pref[0] = 0 for i = 0 .. n-1: pref[i+1] = pref[i] + a[i] sum(i,j) = pref[j+1] - pref[i] dp = [[0]*n for _ in range(n)] for i = 0 .. n-1: dp[i][i] = a[i] for length = 2 .. n: for i = 0 .. n-length: j = i + length - 1 left = a[i] + (sum(i+1,j) - dp[i+1][j]) right = a[j] + (sum(i, j-1) - dp[i][j-1]) dp[i][j] = max(left, right) return dp[0][n-1]

Correctness proof (sketch). Induction on the length of the remaining interval. • Base length=1: only one digit, the formula returns it. • Inductive step: assume the formula is correct for all intervals shorter than ℓ. For interval [i,j] (length ℓ) the optimal first move is either left or right digit; after it, the game on the smaller interval is optimally solved (by the induction hypothesis) giving the opponent dp[…] points, leaving the first player the rest of the sum. Taking the maximum of the two possibilities is therefore optimal, so the recurrence gives the true value. Complexity. There are Θ(n²) interval states and each is filled in O(1) time ⇒ total O(n²) time and O(n²) memory (or O(n) with the 1-D trick).

Back to Chapter 10