265.paint-house-ii.md

假如有一排房子，共 n 个，每个房子可以被粉刷成 k  种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。

当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x k 的矩阵来表示的。

例如，costs[0][0] 表示第 0 号房子粉刷成 0 号颜色的成本花费；costs[1][2]  表示第 1 号房子粉刷成 2 号颜色的成本花费，以此类推。请你计算出粉刷完所有房子最少的花费成本。

注意：

所有花费均为正整数。

示例：

输入: [[1,5,3],[2,9,4]]
输出: 5
解释: 将 0 号房子粉刷成 0 号颜色，1 号房子粉刷成 2 号颜色。最少花费: 1 + 4 = 5;
     或者将 0 号房子粉刷成 2 号颜色，1 号房子粉刷成 0 号颜色。最少花费: 3 + 2 = 5.

进阶：

• 您能否在  O(nk) 的时间复杂度下解决此问题？

---

序列型动态规划

状态机

求出上一状态的最小值和次小值，当前粉刷要么取最小值要么取次小值，跟最小值同一列的时候取次小值

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

        for (int i = 1; i < n; i++) {
            // 求上一行的最小值和次小值
            int first = 0;
            int second = 1;
            if (costs[i - 1][0] > costs[i - 1][1]) {
                first = 1;
                second = 0;
            }
            for (int p = 2; p < k; p++) {
                if (costs[i - 1][p] <= costs[i - 1][first]) {
                    second = first;
                    first = p;
                } else if (costs[i - 1][p] > costs[i - 1][first] && costs[i - 1][p] < costs[i - 1][second]) {
                    second = p;
                }
            }
            for (int j = 0; j < k; j++) {
                if (j == first) {
                    costs[i][j] += costs[i - 1][second];
                } else {
                    costs[i][j] += costs[i - 1][first];
                }
            }
        }
        int ans = costs[n - 1][0];
        for (int j = 1; j < k; j++) {
            ans = min(ans, costs[n - 1][j]);
        }
        return ans;
    }
};