∞ /notes/complexity | 2006-11-10 | algorithms

Complexity

After having failed on it in the actual match miserably, here are three solutions, each with improved runtime behaviour: (Problem: http://www.topcoder.com/stat?c=problem_statement&pm=6680&rd=10005&rm=250175&cr=10496944).

// simple recursive solution
public class RGBStreet {
    private String[] houses;
    public int estimateCost(String[] houses) {
        this.houses = houses;
        int rec = rec(0, -1);
        return rec;
    }
    int rec(int index, int last) {
        if (index == houses.length) {
            return 0;
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < 3; i++) {
            if (last != i) {
                min = Math.min(min, rec(index + 1, i) + cost(index, i));
            }
        }
        return min;
    }
    private int cost(int index, int i) {
        return Integer.parseInt(houses[index].split(" ")[i]);
    }
}

// memoized recursive solution
public class RGBStreet {
    private String[] houses;
    // memoization table
    int[][] best;
    public int estimateCost(String[] houses) {
        this.houses = houses;
        // initialize the memoization table
        best = new int[3][houses.length];
        for (int i = 0; i < best.length; i++) {
            Arrays.fill(best[i], Integer.MAX_VALUE);
        }
        int rec = rec(0, -1);
        return rec;
    }
    int rec(int index, int last) {
        // we are done:
        if (index == houses.length) {
            return 0;
        }
        // we found an optimal solution for painting the current house, given
        // the previous color before:
        if (last != -1 && best[last][index] < Integer.MAX_VALUE)
            return best[last][index];
        // search the best solution for every allowed color for the rest:
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < 3; i++) {
            if (last != i) {
                min = Math.min(min, rec(index + 1, i) + cost(index, i));
            }
        }
        // memoize the solution found:
        if (last != -1)
            best[last][index] = min;
        return min;
    }
    private int cost(int index, int i) {
        return Integer.parseInt(houses[index].split(" ")[i]);
    }
}

// dynamic programming solution
public class RGBStreet {
    public int estimateCost(String[] houses) {
        int[][] matrix = new int[3][houses.length];
        for (int i = 0; i < matrix.length; i++) {
            Arrays.fill(matrix[i], Integer.MAX_VALUE);
            matrix[i][0] = Integer.parseInt(houses[0].split(" ")[i]);
        }
        for (int i = 1; i < houses.length; i++) {
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 3; k++) {
                    if (k != j) {
                        int cost = Integer.parseInt(houses[i].split(" ")[k]);
                        int recentValue = matrix[k][i];
                        int newValue = matrix[j][i - 1] + cost;
                        matrix[k][i] = Math.min(recentValue, newValue);
                    }
                }
            }
        }
        return Math.min(Math.min(matrix[0][houses.length - 1],
                matrix[1][houses.length - 1]), matrix[2][houses.length - 1]);
    }
}