首页 > itarticle > algorithm notes: leetcode#256 paint house

algorithm notes: leetcode#256 paint house

admin 11月 12, 2020 0

Problem

Solution

Initial thoughts

Python implementation

class :
    def minCost(self, costs):
        """
        :type costs: List[List[int]]
        :rtype: int
        """
        if len(costs) == 0:
            return 0
        dp = [costs[0]] + [[0]*3 for _ in range(len(costs)-1)]
        for i in range(1, len(costs)):
            dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + costs[i][0]
            dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + costs[i][1]
            dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + costs[i][2]
        return min(dp[-1])

Java implementation

class  {
    public int minCost(int[][] costs) {
        if(costs.length == 0){ return 0; }
        int[][] dp = costs;
        for(int i = 1; i < dp.length; i++){
            dp[i][0] += dp[i-1][1] < dp[i-1][2] ? dp[i-1][1] : dp[i-1][2];
            dp[i][1] += dp[i-1][0] < dp[i-1][2] ? dp[i-1][0] : dp[i-1][2];
            dp[i][2] += dp[i-1][1] < dp[i-1][0] ? dp[i-1][1] : dp[i-1][0];
        }
        int ans = dp[dp.length-1][0] < dp[dp.length-1][1] ? dp[dp.length-1][0] : dp[dp.length-1][1];
        ans = ans < dp[dp.length-1][2] ? ans : dp[dp.length-1][2];
        return ans;
    }
}

Time complexity

O(N).

Space complexity

O(N).

Links

256. Paint House