6-line Python solution

  • 0

    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]

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.