Python DP solution - 1036ms


  • 0
    H

    Use the recurrence - dp[i][j] = min{i<= k<= j} (k + max(dp[i][k - 1], dp[k + 1][j]))

    class Solution(object):
        def getMoneyAmount(self, n):
            """
            :type n: int
            :rtype: int
            """
            MAX = float('inf')
            # dp array, dp[i][j] represents the min price for guessing number between i and j
            dp = [[0 for i in range(n + 1)] for j in range(n + 1)]
            
            for d in range(1, n):
                for i in range(1, n - d + 1):
                    j = i + d
                    price = MAX
                    for k in range(i, j + 1):
                        price = min(price, 
                                    k + max(0 if (k == i) else dp[i][k - 1],
                                            0 if (k == j) else dp[k + 1][j]))
                        
                    dp[i][j] = price
            
            return dp[1][n]
    

Log in to reply
 

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