Paint Fence / House

Paint Fence

n = 0时，0种可能；n = 1时，k种可能；n = 2时，k * k种可能(其中k种是两个木头一种颜色，另k * (k - 1)种是两个木头不同颜色)。所以第n个木头时，有可能是和前一根木头的颜色相同，也可能和前一根木头的颜色不同。currentSameColor = prevDiffColor, currentDifffColor = (prevSameColor + prevDiffColor) * (k - 1)。

public class Solution {
    public int numWays(int n, int k) {
        if (n == 0 || k == 0) {
            return 0;
        } else if (n == 1) {
            return k;
        }

        int sameColor = k;
        int diffColor = k * (k - 1);

        for (int i = 3; i <= n; i++) {
            int temp = diffColor;
            diffColor = (sameColor + diffColor) * (k - 1);
            sameColor = temp;
        }

        return sameColor + diffColor;
    }
}

或者换一种思考过程，在刷第n块栅栏的时候，要么和n - 1的颜色不一样，要么和n - 2的颜色不一样。

满足“颜色不一样”的选择，显然是k - 1种，于是：

T(n) = (k - 1) * (T[n - 1] + T[n - 2])

public class Solution {
    public int numWays(int n, int k) {
        if (n == 0 || k == 0) {
            return 0;
        } else if (n == 1) {
            return k;
        } else if (n == 2) {
            return k * k;
        }

        int[] dp = new int[3];
        dp[1] = k;
        dp[2] = k * k;

        for (int i = 3; i <= n; i++) {
            dp[i % 3] = (dp[(i - 1) % 3] + dp[(i - 2) % 3]) * (k - 1);
        }
        return dp[n % 3];
    }
}

Paint House

刷房子不能用greedy的思想，因localMin会因为下一个刷的房子使得最终的value很大，而你却不能回头了，所以还是要记录当前位置上，刷每一种颜色的value，为了下一步的更新能选取到最小值。

public class Solution {
    public int minCost(int[][] costs) {
        if (costs == null || costs.length == 0) {
            return 0;
        }

        int red = costs[0][0]; // the minimum cost when the ith house painted with red
        int blue = costs[0][1]; // the minimum cost when the ith house painted with blue
        int green = costs[0][2]; // the minimum cost when the ith house painted with green

        for (int i = 1; i < costs.length; i++) {
            int tempRed = red, tempBlue = blue, tempGreen = green;
            red = Math.min(tempBlue, tempGreen) + costs[i][0];
            blue = Math.min(tempRed, tempGreen) + costs[i][1];
            green = Math.min(tempRed, tempBlue) + costs[i][2];
        }

        return Math.min(red, Math.min(green, blue));
    }
}

Paint House II

和上一题的思路一样，可是如果每次当前轮，都要去扫一遍上一轮的有别人当前颜色的最小值的话，时间复杂度是O(n * k * k)。我们可以通过记录上一轮的minIndex和secondMinIndex把复杂度优化到O(n * k)。如果当前的index为min的话，我们就把当前值加上上一轮的secondMIn，否则就加上min。

public class Solution {
    public int minCostII(int[][] costs) {
        if (costs == null || costs.length == 0) {
            return 0;
        }

        int min = -1, secondMin = -1;
        int n = costs.length, k = costs[0].length;

        for (int i = 0; i < n; i++) {
            int currentMin = -1, currentSecondMin = -1;
            for (int j = 0; j < k; j++) {
                if (j != min) {
                    costs[i][j] += min == -1 ? 0 : costs[i - 1][min];
                } else {
                    costs[i][j] += costs[i - 1][secondMin];
                }

                if (currentMin == -1 || costs[i][j] < costs[i][currentMin]) {
                    currentSecondMin = currentMin;
                    currentMin = j;
                } else if (currentSecondMin == -1 || costs[i][j] < costs[i][currentSecondMin]) {
                    currentSecondMin = j;
                }
            }
            min = currentMin;
            secondMin = currentSecondMin;
        }

        return costs[n - 1][min];
    }
}