相邻房子不能同色，共有3种颜色

There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a nx3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red; costs[1][2] is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

int minCost(vector<vector<int>>& costs) {
    // 设dp[i][c]表示前[0..i]房子、第i房颜色为c时的最小代价
    // 有dp[i][c]=min(dp[i-1][not_c])+costs[i][c]
    // 初始dp[0][c]=costs[0][c]
    // 递推式在i维上只依赖i-1项，省掉i这维，i仍从左往右遍历
    // c这维的依赖方向不确定，要用临时变量ndp[]
    // ndp[c]=min(dp[not_c])+costs[i][c]
    if (costs.empty()) return 0;
    const int N = costs.size(), C = costs[0].size();
    vector<int> dp = costs[0];
    for (int i = 1; i < N; i++) {
        vector<int> ndp(C);
        for (int c = 0; c < C; c++) {
            ndp[c] = min(dp[(c+1) % C], dp[(c+2) % C]) + costs[i][c];
        }
        swap(dp, ndp);
    }
    return min({dp[0], dp[1],dp[2]});
}

相邻房子不能同色，共有k种颜色

There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a nxk cost matrix. For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2]is the cost of painting house 1 with color 2, and so on... Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

Follow up:
Could you solve it in O(nk) runtime?

同上题。可优化成O(nk)解法。

int minCostII(vector<vector<int>>& costs) {
    // 设dp[i][c]表示前[0..i]房子、第i房颜色为c时的minCost
    // dp[i][c] = min{ dp[i-1][not_c] } + costs[i][c]，初始dp[0][c] = costs[0][c]
    // 而求min{ dp[i-1][not_c] }，只要维护dp[i-1][]的最小min1、取min1时的颜色min1c、以及第二小min2
    // 这样 min{ dp[i-1][not_c] } = (c != min1c ? min1 : min2)
    // dp[i][c] = (c != min1c ? min1 : min2) + costs[i][c]
    // 所求为dp[N-1][]的最小min1
    if (costs.empty()) return 0;
    const int N = costs.size(), K = costs[0].size();
    int min1 = 0, min1c = -1, min2 = 0;
    for (int i = 0; i < N; i++) {
        int tmp_min1 = INT_MAX, tmp_min1c = -1, tmp_min2 = INT_MAX; // dp[i][]对应的一组值
        for (int c = 0; c < K; c++) {
            int cost = (c != min1c ? min1 : min2) + costs[i][c];
            if (cost < tmp_min1) {
                tmp_min2 = tmp_min1;
                tmp_min1 = cost;
                tmp_min1c = c;
            } else if (cost < tmp_min2) {
                tmp_min2 = cost;
            }
        }
        min1 = tmp_min1, min1c = tmp_min1c, min2 = tmp_min2;
    }
    return min1;
}

相邻3根栏杆不能同色

There is a fence with n posts, each post can be painted with one of the k colors.

You have to paint all the posts such that no 3 adjacent fence posts have the same color.

Return the total number of ways you can paint the fence.

Note:
n and k are non-negative integers.

int numWays(int n, int k) {
    // 题目：不能有连续三根杆同色
    // 漆第i新杆时，根据前两根杆同色或不同色分情况讨论。
    // 设前两根同色的子问题的上色方式数为dp[i][0]
    //        不同色                  dp[i][1]
    // 若新杆与前一根同色，则前两根不能同色，dp[i][0] = dp[i-1][1]
    // 新杆与前一根不同色，则前两根可同色可不同色，新杆有k-1种选择
    // dp[i][1] = (dp[i-1][0] + dp[i-1][1]) * (k-1)
    // 递推式在i维上只依赖i-1项，省掉i这维
    // ndp[0] = dp[1]
    // ndp[1] = (dp[0] + dp[1]) * (k-1)
    if (n == 0) return 0;
    if (n == 1) return k;
    vector<int> dp = { k, k * (k - 1) }; // n==2的情况
    for (int i = 3; i <= n; i++) {
        dp = { dp[1],  (dp[0] + dp[1]) * (k - 1)};
    }
    return dp[0] + dp[1];
}