```
# 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)
```