package com.interview.dynamic;

/**
 * Paint House 2
 * https://leetcode.com/problems/paint-house-ii/
 */
public class PaintHouse {
    public int minCost(int[][] costs) {
        if (costs.length == 0 || costs[0].length == 0) {
            return 0;
        }
        int[][] dp = new int[costs.length][costs[0].length];
        for (int i = 0; i < costs[0].length; i++) {
            dp[0][i] = costs[0][i];
        }

        for (int i = 1; i < costs.length; i++) {
            Pair p = findMinSecondMin(dp[i - 1]);
            for (int j = 0; j < costs[0].length; j++) {
                dp[i][j] = costs[i][j];
                if (j == p.minIndex) {
                    dp[i][j] += dp[i-1][p.secondMinIndex];
                } else {
                    dp[i][j] += dp[i-1][p.minIndex];
                }
            }
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < dp[0].length; i++) {
            min = Math.min(min, dp[dp.length - 1][i]);
        }
        return min;
    }

    class Pair {
        int minIndex;
        int secondMinIndex;
    }

    private Pair findMinSecondMin(int[] input) {
        int minIndex;
        int secondMinIndex;
        if (input[0] < input[1]) {
            minIndex = 0;
            secondMinIndex = 1;
        } else {
            minIndex = 1;
            secondMinIndex = 0;
        }
        for (int i = 2; i < input.length; i++) {
            if (input[i] < input[minIndex]) {
                secondMinIndex = minIndex;
                minIndex = i;
            } else if (input[i] < input[secondMinIndex]) {
                secondMinIndex = i;
            }
        }
        Pair p = new Pair();
        p.minIndex = minIndex;
        p.secondMinIndex = secondMinIndex;
        return p;
    }

    public static void main(String args[]) {
        PaintHouse ph = new PaintHouse();
        int[][] input = {{1, 2, 1}, {1, 4, 5}, {2, 6, 1}, {3, 3, 2}};
        System.out.println(ph.minCost(input));
    }
}

@@ -46,16 +46,62 @@
 House 2%0A
+ * https://leetcode.com/problems/paint-house/%0A
  * https
@@ -167,24 +167,25 @@
 aintHouse %7B%0A
+%0A
     public i
@@ -194,16 +194,877 @@
  minCost
+TopDownPainHouse1(int%5B%5D%5B%5D costs) %7B%0A        if (costs.length == 0) %7B%0A            return 0;%0A        %7D%0A        int%5B%5D%5B%5D dp = new int%5Bcosts.length%5D%5B3%5D;%0A        return minCostUtil(costs, 0, -1, dp);%0A    %7D%0A%0A    private int minCostUtil(int%5B%5D%5B%5D costs, int house, int prevColor, int%5B%5D%5B%5D dp) %7B%0A        if (house == costs.length) %7B%0A            return 0;%0A        %7D%0A        int min = Integer.MAX_VALUE;%0A        for (int i = 0; i %3C= 2; i++) %7B%0A            if (i == prevColor) %7B%0A                continue;%0A            %7D%0A            int val;%0A            if (dp%5Bhouse%5D%5Bi%5D != 0) %7B%0A                val = dp%5Bhouse%5D%5Bi%5D;%0A            %7D else %7B%0A                val = costs%5Bhouse%5D%5Bi%5D + minCostUtil(costs, house + 1, i, dp);%0A                dp%5Bhouse%5D%5Bi%5D = val;%0A            %7D%0A            min = Math.min(min, val);%0A        %7D%0A        return min;%0A    %7D%0A%0A    public int minCostBottomUpPaintHouse2
 (int%5B%5D%5B%5D
@@ -2873,16 +2873,35 @@
 .minCost
+BottomUpPaintHouse2
 (input))

Update paint house