MinimumCost.java

public class MinimumCost {

    public static void main(String[] args) {
        int[][] matrix = new int[][]{{17, 2, 17}, {16, 16, 5}, {14, 3, 19}};
        System.out.println(findMinimumCost(matrix));
    }

    private static int findMinimumCost(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        // Rows
        int n = matrix.length;
        // Columns
        int k = matrix[0].length;

        // This represents minimum cost of any color (0,1,2,3...k)
        int[] minColorCost = new int[k];

        // Most minimum value at the previous stage
        int min = 0;
        // Second most minimum value at the previous stage
        int secondMin = 0;

        for (int i = 0; i < matrix.length; i++) {
            // Keeping reference of the previous stage minimums
            int x = min;
            int y = secondMin;

            min = Integer.MAX_VALUE;
            secondMin = Integer.MAX_VALUE;

            // Loop for each color
            for (int j = 0; j < k; j++) {
                if (minColorCost[j] != x || x == y) {
                    minColorCost[j] = x + matrix[i][j];
                } else {
                    minColorCost[j] = y + matrix[i][j];
                }

                if (min <= minColorCost[j]) {
                    y = Math.min(y, minColorCost[j]);
                } else {
                    secondMin = min;
                    min = minColorCost[j];
                }
            }
        }
        return min;
    }
}