Minimum Cost Selection

Problem Overview

Each row has three options and you cannot pick the same option as the previous row.

Intuition

Each row has three options and you cannot pick the same option as the previous row. That is the classic paint-house recurrence: the cheapest way to end row i on color j is mat[i][j] plus the better of the two costs from the other colors on row i-1. Only the previous row matters, so keep three rolling values.

Algorithm

1Set prev0, prev1, prev2 from the first row.
2For each later row i: curr0 = mat[i][0] + min(prev1, prev2), curr1 = mat[i][1] + min(prev0, prev2), curr2 = mat[i][2] + min(prev0, prev1).
3Shift curr into prev.
4Return min(prev0, prev1, prev2).

Example Walkthrough

Input: mat = [[1,5,3],[2,9,4],[3,6,2]]

1. Row 0 costs are 1, 5, 3.
2. Row 1: color 0 costs 2+3=5, color 1 costs 9+1=10, color 2 costs 4+1=5.
3. Row 2: best ends on color 0 with 3+4=7.

Output: 7

Common Pitfalls

• Each new color must differ from the previous row, not from its neighbors in the same row.
• Initialize from row 0 directly; there is no row -1.
• The answer is the minimum of the three final states, not any single column sum.
• Use long only if costs can overflow int; typical GFG constraints fit in int.

Minimum Cost Selection.java

Java

// Approach: Paint-house DP with 3 choices per row. dp[j] = min cost to paint
// row i with color j, using a different color on row i-1. Roll three states per
// row instead of a full table.
// Complexity: O(n) time and O(1) extra space (n = number of rows).

class Solution {

    public int minCost(int[][] mat) {
        int prev0 = mat[0][0];
        int prev1 = mat[0][1];
        int prev2 = mat[0][2];

        for (int i = 1; i < mat.length; i++) {
            int curr0 = mat[i][0] + Math.min(prev1, prev2);
            int curr1 = mat[i][1] + Math.min(prev0, prev2);
            int curr2 = mat[i][2] + Math.min(prev0, prev1);

            prev0 = curr0;
            prev1 = curr1;
            prev2 = curr2;
        }

        return Math.min(prev0, Math.min(prev1, prev2));
    }
}

Was this solution helpful?