BU

class Solution:
    def getMoneyAmount(self, n: int) -> int:
        dp = [[0] * (n+1) for _ in range(n+1)]
        for length in range(2, n+1):
            for start in range(1, n-length+2):
                end = start + length - 1
                dp[start][end] = min(i + max(dp[start][i-1], dp[i+1][end]) for i in range(start, end))
        return dp[1][n]