General algorithm – [game theory] – two – number game

1. Problem description

Given an array nums, a and B take turns picking a number from either the left or right end of the array as their score. Assuming they are both smart enough to use the optimal strategy, and a takes first, what is the maximum score that A can get? Example:

Input: nums=[4,7,5,3] output: 10 explanation: the maximum score a can get is 7+3=10.

2

We can make clear the following points: (1) when the player aaa, BBB in subarray nums nums [I,…, j] [I,…, j] nums in [I,…, j] access, no matter how to take, aaa, BBB, the final score is always a fixed value, the sum of the fixed value equal to the child the sum of all the elements of an array of; (2) suppose dp [I] [j] dp [I] [j] dp [I] [j] said aaa player in subarray nums nums [I,…, j] [I,…, j] nums [I,…, j] take the number of the optimal solution, because the BBB player each time and choose the optimal solution, So dp [I – 1] [j] dp [j] [I – 1] dp [j] or [I – 1] dp [I] [j – 1] dp [I] [1] dp [I] [j – 1) represents the BBB in subarray Nums [I,…, j] nums nums [I,…, j] [I,…, j] take the number of the optimal solution (because the aaa players left after took a number of elements is either nums nums [I + 1,…, j] [I + 1,…, j] nums [I + 1,…, j] either Nums nums [I,…, j – 1] [I,…, j – 1] nums [I,…, j – 1]). (3) Considering that the sum of scores of AAA and BBB is fixed, i.e. the score of AAA plus the score of BBB equals a fixed value, the highest score of AAA players is equivalent to the lowest score of BBB players.

According to the above conclusions, we adopt dynamic programming to solve this problem: (1) Define the state:

Dp [I] [j] dp [I] [j] dp [I] [j] : aaa player in subarray nums nums [I,…, j] [I,…, j] nums [I,…, j] take the number of maximum score;

(2) State transfer: Aaa player in subarray nums nums [I,…, j] [I,…, j] nums [I,…, j] score equal to the sum of subarray sum (I, j) sum (I, j) sum (I, j) minus the BBB subarray Nums [I,j]nums[I,j], and aaa players want the highest score, equivalent to BBB players have the lowest score.

$dp[i][j] = sum(i,j) – min(dp[i+1][j],dp[i][j-1])$

(3) Determine the start: when there is only one number left, AAA takes it. Dp [I] [I] = nums dp [I] [I] [I] = nums dp [I] [I] [I] = nums [I]. (4) Determine the maximum score of the terminated AAA player in the entire array. Dp dp [0] [length – 1] [0] [] length – 1 dp [0] [length – 1)

Note that since the sums of interval arrays are involved, you can optimize with prefix sums.

3. Code implementation

int maxScore(vector<int> nums){
	int len = nums.size(a);// Find the prefix and array
	vector<int> sums(len,0);
	for(int i = 0; i < len; i++){
		if(i > 0){
			sums[i] = sums[i- 1] + nums[i]
		}
		else{ sums[i] = nums[i]; }}// Dynamic programming
	vector<vector<int>> dp(len, vector<int>(len,0));
	for(int i = 0; i < len; i++){
		for(int j=i; j >=0; j--){
			if(j == i){
				dp[i][i] = nums[i];
			}
			else{
				int scoresum = j  > 0 ? sum[i] - sum[j- 1] : sum[i];
				dp[j][i] = scoresum - min(dp[j+1][i],dp[j][i- 1]; }}}return dp[0][len - 1];
			
}
Copy the code