Simple Python 2-dim DP - can't think of a "non-substring" type of solution


  • 0
    A
    class Solution(object):
        def getMoneyAmount(self, n):
            """
            :type n: int
            :rtype: int
            """
            dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
            for lo in range(1, n):
                dp[lo][lo+1] = lo
            for diff in range(2, n):
                for lo in range(1, n-diff+1):
                    hi = lo + diff 
                    gMax = (lo+hi)*(diff+1)/2
                    for j in range(lo+1, hi):
                        left, right = dp[lo][j-1], dp[j+1][hi]
                        gMax = min(gMax, j + max(left, right))
                    dp[lo][hi] = gMax
            return dp[1][n]
    

Log in to reply
 

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