Leetcode 265 Solution

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

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

Solution

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

        int n = costs.size();
        int k = costs[0].size();

        int dp[n][k];
        int min_vals1[k] = {0};
        int min_vals2[k] = {0};

        for (int i = 0; i < n; i++)
        {
            if (i == 0)
            {
                for (int j = 0; j < k; j++)
                    dp[i][j] = costs[i][j];
            }
            else
            {
                for (int j = 0; j < k; j++)
                    min_vals1[j] = j == 0 ? INT_MAX : min(dp[i - 1][j - 1], min_vals1[j - 1]);

                for (int j = k - 1; j >= 0; j--)
                    min_vals2[j] = j == k - 1 ? INT_MAX : min(dp[i - 1][j + 1], min_vals2[j + 1]);

                for (int j = 0; j < k; j++)
                    dp[i][j] = min(min_vals1[j], min_vals2[j]) + costs[i][j];
            }
        }

        int min_val = INT_MAX;
        for (int j = 0; j < k; j++)
            min_val = min(min_val, dp[n - 1][j]);

        return min_val;
    }
};