subject

describe

Given an integer array arr, which represents cards of different values, a line is formed. Player A and Player B take each card in turn, requiring Player A to take it first and Player B to take it later, but each player can only take the left or right card at a time. Player A and Player B are brilliant. Return to the winner's score.
[Example]
arr=[1,2,100,4].
Player A can only take 1 or 4 at the beginning. If Player A takes 1 at the beginning, the alignment changes to [2,100,4]. Player B can take 2 or 4 then continue to take Player A's turn.
If Player A takes away 4 at the beginning, the alignment changes to [1,2,100], then Player B can take away 1 or 100, and then continue to take Player A's turn...
Player A, as the ultimate smart person, won't take 4 first because Player B will take 100 after taking 4. So Player A will take 1 first and change the alignment to [2,100,4]. Player B will take 100 away by Player A whatever he chooses. Player A will win with a score of 101. So go back to 101.
arr=[1,100,2].
Player A starts with 100 as the smartest person, taking either 1 or 2. Player B wins with a score of 100. So return to 100.

Solving problems

(1) Recursion problems For ease of understanding, you can list the entire process of recursion

(2) Set the input arr to [1, 8, 10, 6]

(3) using the win function to find the optimal solution of arr, that is, to get the optimal solution first in hand and then in hand

(4) where 0 and 3 represent a double pointer to the front and back values of the array

>>>win([1, 8, 10, 6], 4)
max(f([1, 8, 10, 6], 0, 3), s([1, 8, 10, 6], 0, 3))

(5) For the first-hand f-function, it resolves to take the left or the right so that it has the largest result and can be converted to,

>>>f([1, 8, 10, 6], 0, 3)
max(1 + s([1, 8, 10, 6], 1, 3), 6 + s([1, 8, 10, 6], 0, 2))

(6) For the second-hand s-function, it resolves to take the left or the right, so that the result of the opponent is the smallest and can be converted to

>>>s([1, 8, 10, 6], 0, 3)
min(f([1, 8, 10, 6], 1, 3), f([1, 8, 10, 6], 0, 2))

(7) Similarly, 1,3 means taking the card on the left, 0,2 means taking the card on the right.

>>>1 + s([1, 8, 10, 6], 1, 3)
1 + min(f([1, 8, 10, 6], 2, 3), f([1, 8, 10, 6], 1, 2))

>>>6 + s([1, 8, 10, 6], 0, 2)
6 + min(f([1, 8, 10, 6], 1, 2), f([1, 8, 10, 6], 0, 1))

>>>f([1, 8, 10, 6], 1, 3)
max(8 + s([1, 8, 10, 6], 2, 3), 6 + s([1, 8, 10, 6], 1, 2))

>>>f([1, 8, 10, 6], 0, 2)
max(1 + s([1, 8, 10, 6], 1, 2), 10 + s([1, 8, 10, 6], 0, 1))

(8) List further below

>>>f([1, 8, 10, 6], 2, 3)
max(10 + s([1, 8, 10, 6], 3, 3), 6 + s([1, 8, 10, 6], 2, 2))
max(10, 6)
10

>>>f([1, 8, 10, 6], 1, 2)
max(8 + s([1, 8, 10, 6], 2, 2), 10 + s([1, 8, 10, 6], 1, 1))
max(8, 10)
10

>>>f([1, 8, 10, 6], 1, 2)
max(8 + s([1, 8, 10, 6], 2, 2), 10 + s([1, 8, 10, 6], 1, 1))
max(8, 10)
10

>>>f([1, 8, 10, 6], 0, 1)
max(1 + s([1, 8, 10, 6], 0, 0), 8 + s([1, 8, 10, 6], 1, 1))
max(1, 8)
8

>>>s([1, 8, 10, 6], 2, 3)
min(f([1, 8, 10, 6], 3, 3), f([1, 8, 10, 6], 2, 2))
min(6, 10)
6

>>>s([1, 8, 10, 6], 1, 2)
min(f([1, 8, 10, 6], 2, 2), f([1, 8, 10, 6], 1, 1))
min(10, 8)
8

>>>s([1, 8, 10, 6], 1, 2)
min(f([1, 8, 10, 6], 2, 2), f([1, 8, 10, 6], 1, 1))
min(10, 8)
8

>>>s([1, 8, 10, 6], 0, 1)
min(f([1, 8, 10, 6], 1, 1), f([1, 8, 10, 6], 0, 0))
min(8, 1)
1

(9) Return to calculation result (7)

>>> 1 + s([1, 8, 10, 6], 1, 3)
1 + min(f([1, 8, 10, 6], 2, 3), f([1, 8, 10, 6], 1, 2))
1 + min(10, 10)
11

>>> 6 + s([1, 8, 10, 6], 0, 2)
6 + min(f([1, 8, 10, 6], 1, 2), f([1, 8, 10, 6], 0, 1))
6 + min(10, 8)
14

>>> f([1, 8, 10, 6], 1, 3)
max(8 + s([1, 8, 10, 6], 2, 3), 6 + s([1, 8, 10, 6], 1, 2))
max(14, 14)
14

>>> f([1, 8, 10, 6], 0, 2)
max(1 + s([1, 8, 10, 6], 1, 2), 10 + s([1, 8, 10, 6], 0, 1))
max(9, 11)
11

(10) Back to step (5)

>>>f([1, 8, 10, 6], 0, 3)
max(1 + s([1, 8, 10, 6], 1, 3), 6 + s([1, 8, 10, 6], 0, 2))
max(11, 14)
14

(11) Return to step (6)

>>>s([1, 8, 10, 6], 0, 3)
min(f([1, 8, 10, 6], 1, 3), f([1, 8, 10, 6], 0, 2))
min(14, 11)
11

(12) Therefore, the optimal score scheme is to hold the card first, take 6 then 8, with a score of 14, and take only 10 and 1 for the later scheme, with a score of 11.

Code

def win(arr, sz):
    if sz == 0:
        return 0
    else:
        return max(f(arr, 0, sz - 1), s(arr, 0, sz - 1))

#First hand
def f(arr, i, j):
    if i == j:
        return arr[i]
    else:
        return max(arr[i] + s(arr, i + 1, j), arr[j] + s(arr, i, j - 1))

#Backhand
def s(arr, i, j):
    if i==j:#Indicates that you have taken it first and there is only one situation left
        return 0
    else:
        return min(f(arr, i + 1, j), f(arr, i, j - 1))#First you want to win, then you need to take the worst

if __name__=="__main__":
    arr = [1, 8, 10, 6]
    print(win(arr, len(arr)))