Python o(nk) solution, use min(left_min,right_min).

  • 0

    The idea is simple.

    use dp[i] = min(left[i],right[i]) + cost

    left[i] means the min cost on [0,i) of last round.

    right[i] means the min cost on (i,n) of last round.


    class Solution:
        # @param {integer[][]} costs
        # @return {integer}
        def minCostII(self, costs):
            max_int = 2147483647
            n = len(costs)
            if n <= 0:
                return 0
            k = len(costs[0])
            left = [0 for i in xrange(k)]
            right = [0 for i in xrange(k)]
            dp = [ 0 for i in xrange(k)]
            for i in xrange(n):
                for j in xrange(k):
                    dp[j] = min(left[j],right[j]) + costs[i][j]
                left[0] = max_int
                for j in xrange(1,k):
                    left[j] = min(dp[j-1],left[j-1])
                right[k-1] = max_int
                for j in xrange(k-2,-1,-1):
                    right[j] = min(dp[j+1],right[j+1])
            ret = dp[0]
            for x in dp:
                ret = min(ret,x)
            return ret

Log in to reply

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