LinkedIn: Find Pythagorean Triplets in an array

Discussion

Follow up

如果是用K用颜色paiting呢？

每次迭代house i前先计算出dp[i-1][]的最小值和次小值， 则递推式简化为dp【i】[j]=(dp[i-1][j] == preMin ? preSecondMin : preMin) + costs【i】[j] 如果dp[i-1][j]正好是刷前面所有house的最小值，由于相邻house不能同色，那这次我们就要用次小值（运气好，可能和最小值相等~）

// Time:  O(n * k)
// Space: O(k)

class Solution {
public:
    int minCostII(vector<vector<int>>& costs) {
        if (costs.empty()) {
            return 0;
        }

        vector<vector<int>> min_cost(2, costs[0]);

        const int n = costs.size();
        const int k = costs[0].size();
        for (int i = 1; i < n; ++i) {
            int smallest = INT_MAX, second_smallest = INT_MAX;
            //1. find out preMin, preSecondMin
            for (int j = 0; j < k; ++j) {
                if (min_cost[(i - 1) % 2][j] < smallest) {
                    second_smallest = smallest;
                    smallest = min_cost[(i - 1) % 2][j];
                } else if (min_cost[(i - 1) % 2][j] < second_smallest) {
                    second_smallest = min_cost[(i - 1) % 2][j];
                }
            }
            //paint houese i with different j? i.e., how to decide smallest or second smallest for each j?
            for (int j = 0; j < k; ++j) {
                const int min_j = (min_cost[(i - 1) % 2][j] != smallest) ? smallest : second_smallest;
                min_cost[i % 2][j] = costs[i][j] + min_j;
            }
        }

        return *min_element(min_cost[(n - 1) % 2].cbegin(), min_cost[(n - 1) % 2].cend());
    }
};