Python dp solutions (O(nk) and O(k) spaces).


  • 0
    C
    # dp, O(nk) space
    def minCostII1(self, costs):
        if not costs:
            return 0
        r, c = len(costs), len(costs[0])
        dp = [[0 for _ in xrange(c)] for _ in xrange(r)]
        dp[0] = costs[0]
        for i in xrange(1, r):
            for j in xrange(c):
                dp[i][j] = costs[i][j] + min(dp[i-1][:j]+dp[i-1][j+1:])
        return min(dp[-1])
        
    # dp, O(k) space
    def minCostII(self, costs):
        if not costs:
            return 0
        r, c = len(costs), len(costs[0])
        cur = costs[0]
        for i in xrange(1, r):
            pre = cur[:]  # take care here
            for j in xrange(c):
                cur[j] = costs[i][j] + min(pre[:j]+pre[j+1:])
        return min(cur)

  • -1
    C
    This post is deleted!

Log in to reply
 

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