# 游戏的最佳策略是最小化你面临的最大可能损失
# 解题方法1：DP
class Solution(object):
    def getMoneyAmount(self, n):
        dp = [[0] * (n+1) for _ in range(n+1)]
        for gap in range(1, n):
            for lo in range(1, n + 1 - gap):
                hi = lo + gap
                dp[lo][hi] = min(x + max(dp[lo][x-1], dp[x+1][hi])
                                        for x in range(lo,hi))
        return dp[1][n]
