双人游戏问题

 有如下一个双人游戏：N个正整数的序列放在一个游戏平台上，两个人轮流从序列的两端取数，取数后该数字被去掉并累加到本玩家的得分中，当数取尽时，游戏结束，以最终的分多者为胜利。编写一个执行最优策略的程序，最优策略就是使得自己能在当前情况下得到最优策略。要求程序要始终为第二位玩家执行最优策略。

该题目的动态规划方程是：

设sum(s,t)为区间s,t中的数字和，gain(s,t)为按照最优策略能获得的最大得分，那么有两种数字的方式：

1，取s,则给对手留下余下的区间是(s+1,t),对手的收益是gain(s+1,t)

2,或者取t,则给对手留下的区间是（s，t-1）,对手的收益是gain(s,t-1)

无论如何，自身得分是sum(s,t)-min{gain(s+1,t),gain(s,t-1)}

def memorize_gain(arr,i,j):
    if i==j:
        memorize[i][j]=arr[i]
        return arr[i]
    if memorize[i+1][j]>0:
        p=memorize[i+1][j]
    else:
        p=memorize_gain(arr,i+1,j)
    if memorize[i][j-1]>0:
        q=memorize[i][j-1]
    else:
        q=memorize_gain(arr,i,j-1)
    memorize[i][j]=sum[i][j]-min(p,q)
    print(i,j,p, q,memorize[i][j])
    return memorize[i][j]
if __name__ == \"__main__\":
    n = int(input())
    # arr=input()
    # arr=[int(n) for n in arr.split()]
    arr = [0 for i in range(n + 1)]
    for i in range(1, n + 1):
        arr[i] = int(input())
    sum = [[0 for i in range(n + 1)] for i in range(n + 1)]
    memorize = [[0 for i in range(n + 1)] for i in range(n + 1)]
    for i in range(1, n + 1):  # 自底向上
        for j in range(i, n + 1):
            sum[i][j] = sum[i][j - 1] + arr[j]
    print(memorize_gain(arr, 1, n), \' \', sum[1][n] - memorize[1][n])