Leetcode 256 Solution

This article provides solution to leetcode question 256 (paint-house)
Categories:
Tags:
Access this page by simply typing in "lcs 256" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/paint-house

Solution

class Solution {
public:
    int minCost(vector<vector<int>>& costs)
    {
        if (costs.size() == 0 || costs[0].size() == 0)
            return 0;

        int m = costs.size();
        int n = costs[0].size();
        vector<vector<int>> dp(m, vector<int>(n));

        for (int i = 0; i < m; i++)
        {
            if (i == 0)
            {
                dp[i][0] = costs[i][0];
                dp[i][1] = costs[i][1];
                dp[i][2] = costs[i][2];
            }
            else
            {
                dp[i][0] = costs[i][0] + min(dp[i - 1][1], dp[i - 1][2]);
                dp[i][1] = costs[i][1] + min(dp[i - 1][0], dp[i - 1][2]);
                dp[i][2] = costs[i][2] + min(dp[i - 1][0], dp[i - 1][1]);
            }
        }

        int min_val = INT_MAX;
        for (int j = 0; j < 3; j++)
            min_val = min(min_val, dp[m - 1][j]);
        return min_val;
    }
};