Skip to content

Instantly share code, notes, and snippets.

# ysinjab/main.py

Last active November 17, 2022 05:53
Show Gist options
• Save ysinjab/1d2e4c95b8070a521ddd395ad7fc785a to your computer and use it in GitHub Desktop.
256. Paint House
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 class Solution: def minCost(self, costs: List[List[int]]) -> int: # recursion # state is the current house we are painting with color c that has a cost + min of prev min # state variables are i, c # recurrence relation : dp(i, c) = cost[c] + min(dp(i + 1, c-1), dp(i + 1, c+1)) # base case: i == len(costs) return 0 # @lru_cache(None) # def dp(i, c): # if i == len(costs): # return 0 # colors = [index for index, d in enumerate(costs[i]) if index != c] # return costs[i][c] + min(dp(i+1, colors[0]), dp(i+1, colors[1])) # return min(dp(0, 0), dp(0, 1), dp(0, 2)) # iterative # dp = [[0] * (len(costs[0])) for _ in range(len(costs) + 1)] # for i in range(1, len(costs) + 1): # for c, _ in enumerate(costs[i-1]): # colors = [index for index, d in enumerate(costs[i-1]) if index != c] # dp[i][c] = costs[i-1][c] + min(dp[i-1][colors[0]], dp[i-1][colors[1]]) # return min(dp[len(costs)]) # iterative with state reduction prev = [0] * 3 for now in costs: prev = [now[i] + min(prev[:i]+prev[i+1:]) for i in range(3)] return min(prev)
to join this conversation on GitHub. Already have an account? Sign in to comment