@@ -0,0 +1,1790 @@
+package com.freetymekiyan.algorithms.level.medium;%0A%0A/**%0A * 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%0A * painting each house with a certain color is different. You have to paint all the houses such that no two adjacent%0A * houses have the same color.%0A * %3Cp%3E%0A * The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs%5B0%5D%5B0%5D%0A * is the cost of painting house 0 with color red; costs%5B1%5D%5B2%5D is the cost of painting house 1 with color green, and so%0A * on... Find the minimum cost to paint all houses.%0A * %3Cp%3E%0A * Note:%0A * All costs are positive integers.%0A * %3Cp%3E%0A * Company Tags: LinkedIn%0A * Tags: Dynamic Programming%0A * Similar Problems: (E) House Robber, (M) House Robber II, (H) Paint House II, (E) Paint Fence%0A */%0Apublic class PaintHouse %7B%0A%0A    /**%0A     * DP.%0A     * Recurrence Relation:%0A     * The color of current house i has 3 possibilities.%0A     * If it's red, the min cost will be cost of red at i + min(cost of blue at i-1, cost of green at i-1).%0A     * That is: costs%5Bi%5D%5B0%5D + min(costs%5Bi - 1%5D%5B1%5D, costs%5Bi - 1%5D%5B2%5D).%0A     * The same goes for if it's blue or green.%0A     * So generate all possibilities.%0A     * Base case:%0A     * If costs matrix is empty, return 0.%0A     */%0A    public int minCost(int%5B%5D%5B%5D costs) %7B%0A        if (costs.length == 0) %7B%0A            return 0;%0A        %7D%0A        int n = costs.length;%0A        for (int i = 1; i %3C n; i++) %7B%0A            costs%5Bi%5D%5B0%5D += Math.min(costs%5Bi - 1%5D%5B1%5D, costs%5Bi - 1%5D%5B2%5D);%0A            costs%5Bi%5D%5B1%5D += Math.min(costs%5Bi - 1%5D%5B0%5D, costs%5Bi - 1%5D%5B2%5D);%0A            costs%5Bi%5D%5B2%5D += Math.min(costs%5Bi - 1%5D%5B1%5D, costs%5Bi - 1%5D%5B0%5D);%0A        %7D%0A        return Math.min(Math.min(costs%5Bn - 1%5D%5B0%5D, costs%5Bn - 1%5D%5B1%5D), costs%5Bn - 1%5D%5B2%5D);%0A    %7D%0A%7D%0A

add paint house