Fork me on GitHub

Paint House II

Posted on

Description

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

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    int minCostII(vector<vector<int>>& costs) {
        int size = costs.size();
        if (size == 0) return 0;
        int colorNumber = costs[0].size();
        
        vector<vector<int>> dp(size + 1, vector<int>(colorNumber, 0));
        pair<int, int> minCost;
        minCost.second = 0;
        minCost.first = -1;
        pair<int, int> secondMinCost;
        secondMinCost.second = 0;
        secondMinCost.first = -1;
        for (int i = 1; i <= size; ++i) {
            int targetIndex = -1;
            int targetCost = INT_MAX;
            int secondIndex = -1;
            int secondCost = INT_MAX;
            for (int j = 0; j < colorNumber; ++j) {
                dp[i][j] = costs[i - 1][j] + 
                    (minCost.first == j ? secondMinCost.second : minCost.second);
                if (dp[i][j] < targetCost) {
                    secondIndex = targetIndex;
                    secondCost = targetCost;
                    targetCost = dp[i][j];
                    targetIndex = j;
                }else if (dp[i][j] < secondCost) {
                    secondIndex = j;
                    secondCost = dp[i][j];
                }
            } 
            minCost.first = targetIndex;
            minCost.second = targetCost;
            secondMinCost.first = secondIndex;
            secondMinCost.second = secondCost;
        }
        
        return minCost.second;
    }
};