Leetcode - 256. Paint House

문제

3종류의 페인트로 집을 칠한다. 주어진 2차원 배열의 row는 각각의 집, colum은 각 3가지 페인트의 가격이 적혀있다. 인접한 집이 서로 같은색이 되지 않도록 칠하는 모든 경우중 가장 저렴한 페인트 총합은?

Input: costs = [[17,2,17],[16,16,5],[14,3,19]]
Output: 10
Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue.
Minimum cost: 2 + 5 + 3 = 10.

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

아이디어 - DP

• 점화식: f(h,c) = min(f(h+1, 다른색1), f(h+1, 다른색2)) + 가격(c)
• 0,1,2 값중 한 값(clr)이 주어질때, 나머지 두 값은 이렇게 계산할 수 있다. (clr + 1) % 3 and (clr + 2) % 3
• 유사문제는
  Leetcode-198.-House-Robber

brute-force

class Solution {
    int minval(int a, int b, int c) {
        int ret = 0;
        if (a < b)
            ret = a;
        else
            ret = b;
        if (c < ret)
            ret = c;
        return ret;
    }
public:
    int paint(vector<vector<int>>& cost, int h, int clr) {
        if (h == cost.size())
            return 0;
        // the other value is always be: (clr + 1) % 3 and (clr + 2) % 3
        return min(paint(cost, h + 1, (clr + 1) % 3), paint(cost, h + 1, (clr + 2) % 3))  + cost[h][clr];
    }
    int minCost(vector<vector<int>>& costs) {
        return minval(paint(costs, 0, 0), paint(costs, 0, 1), paint(costs, 0, 2));
    }
};

memoization

class Solution {
    int minval(int a, int b, int c) {
        int ret = 0;
        if (a < b)
            ret = a;
        else
            ret = b;
        if (c < ret)
            ret = c;
        return ret;
    }
    int vis[101][3] = {0};
public:
    int paint(vector<vector<int>>& cost, int h, int clr) {
        if (h == cost.size())
            return 0;
        if (vis[h][clr])
            return vis[h][clr];
        // the other value is always be: (clr + 1) % 3 and (clr + 2) % 3
        vis[h][clr] = min(paint(cost, h + 1, (clr + 1) % 3), paint(cost, h + 1, (clr + 2) % 3))  + cost[h][clr];
        return vis[h][clr];
    }
    int minCost(vector<vector<int>>& costs) {
        return minval(paint(costs, 0, 0), paint(costs, 0, 1), paint(costs, 0, 2));
    }
};