LC-0375 Medium LeetCode

375. Guess Number Higher or Lower II

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 51% Topics: Math, Dynamic Programming, Game Theory

Reading material

Math & Geometry 12 min 1-D Dynamic Programming 16 min Game Theory 11 min

Reference solution (spoiler · python)

# Time:  O(n^3)
# Space: O(n^2)
class Solution(object):
    def getMoneyAmount(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [[0]*(n+1) for _ in xrange(n+1)]  # dp[i][j]: min pay in [i+1, j+1)
        for j in xrange(n+1):
            for i in reversed(xrange(j-1)):
                dp[i][j] = min((k+1) + max(dp[i][k], dp[k+1][j]) for k in xrange(i, j))
        return dp[0][n]


# Time:  O(n^3)
# Space: O(n^2)
class Solution2(object):
    def getMoneyAmount(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [[0]*(n+1) for _ in xrange(n+1)]  # dp[i][j]: min pay in [i+1, j+1)
        for i in reversed(xrange(n)):
            for j in xrange(i+2, n+1):
                dp[i][j] = min((k+1) + max(dp[i][k], dp[k+1][j]) for k in xrange(i, j))
        return dp[0][n]

Solution from kamyu104/LeetCode-Solutions · MIT