Python fast bottom-up DP


  • 0
    Y

    Consider sequences of numbers in increasing order of length. The cost for lengths 1 and 2 are trivial so precompute them.
    For any greater length we only need to check guesses from the mid-point of the sequence since if the RHS of the sequence is longer we cannot have a minimum cost because the numbers there are greater - optimal solutions must have longer or equal LHS. Also the upper value of the sequence is never optimal because we can only ever eliminate that one guess.
    So take the min of all remaining guess costs where each guess cost is the guess number + max of guessing within LHS and RHS sequences.

        def getMoneyAmount(self, n):
            # min_money[i][j] is min money to guarantee win if search range length is i+1 starting from j+1
            # if length == 1, min_money = 0 since no guess required
            # if length == 2, min_money = lower value of range
            min_money = [[0 for _ in range(n)], [i for i in range(1, n)]]
    
            for range_length in range(3, n + 1):
                min_money.append([])
                for lower in range(1, n + 2 - range_length):
                    upper = lower + range_length - 1
                    min_cost = float('inf')
                    for guess in range((lower + upper)  // 2, upper):   # guesses of LHS and upper are never optimal
                        cost = guess + max(min_money[guess - lower - 1][lower - 1], 
                                                         min_money[upper - guess - 1][guess])
                        min_cost = min(min_cost, cost)                    
                    min_money[-1].append(min_cost)
    
            return min_money[n - 1][0]

Log in to reply
 

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