Fork me on GitHub

Paint House

Posted on

Description

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

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        int size = costs.size();
        if (size == 0) return 0;
        vector<vector<int>> dp(size + 1, vector<int>(3, 0));
        
        for (int i = 1; i <= size; ++i) {
            dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];
            dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1];
            dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i - 1][2];
        }
        
        return min(min(dp[size][0], dp[size][1]), dp[size][2]);
    }
};