The idea is simple: minimax!

```
class Solution(object):
def getMoneyAmount(self, n):
"""
:type n: int
:rtype: int
"""
f = [[0 if j-i <= 0 else float('inf') for j in range(n+2)] for i in range(n+2)]
for l in range(1, n):
for i in range(1, n-l+1):
for g in range(i, i+l+1):
f[i][i+l] = min(f[i][i+l], g + max(f[i][g-1], f[g+1][i+l]))
return f[1][n]
```