Introduction

The Minimum Cost Selection problem is a simple and useful Dynamic Programming (DP) problem.

We are given an n × 3 matrix where each row contains the cost of three choices. We must select exactly one choice from every row, but there is one important restriction:

The same choice cannot be selected in two adjacent rows.

Our goal is to find the minimum possible total cost.

For example:

Code
mat = [
    [1, 4, 1],
    [3, 2, 2],
    [3, 2, 3]
]

One optimal selection is:

Code
Row 1 → Choice 0 → Cost 1
Row 2 → Choice 1 → Cost 2
Row 3 → Choice 2 → Cost 2

Total = 1 + 2 + 2 = 5

Understanding the Problem

Consider a row:

Code
[10, 20, 30]

There are three choices:

Code
Choice 0 → 10
Choice 1 → 20
Choice 2 → 30

If we select Choice 0 in the current row, we cannot select Choice 0 in the previous row.

Therefore, the previous row can only use:

Code
Choice 1 or Choice 2

So the minimum cost for choosing Choice 0 becomes:

Code
current cost + minimum(previous choice 1, previous choice 2)

Similarly:

Code
Choice 0 → mat[i][0] + min(prev1, prev2)

Choice 1 → mat[i][1] + min(prev0, prev2)

Choice 2 → mat[i][2] + min(prev0, prev1)

Dynamic Programming Idea

We don't need to store the complete DP table.

For every row, we only need to know the minimum costs obtained from the previous row.

We maintain three variables:

Java
prev0
prev1
prev2

They represent:

Code
prev0 = minimum cost when previous row ends with Choice 0
prev1 = minimum cost when previous row ends with Choice 1
prev2 = minimum cost when previous row ends with Choice 2

This allows us to achieve O(1) auxiliary space.

Java Solution

Java
class Solution {
    public int minCost(int[][] mat) {
        int n = mat.length;

        // Minimum cost after processing the first row
        int prev0 = mat[0][0];
        int prev1 = mat[0][1];
        int prev2 = mat[0][2];

        // Process remaining rows
        for (int i = 1; i < n; 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);

            // Move current values to previous values
            prev0 = curr0;
            prev1 = curr1;
            prev2 = curr2;
        }

        // Minimum cost among the three choices in the last row
        return Math.min(prev0, Math.min(prev1, prev2));
    }
}

Code Explanation

1. Get the number of rows

Java
int n = mat.length;

n stores the total number of rows.

For example:

Code
mat = [
    [1, 4, 1],
    [3, 2, 2],
    [3, 2, 3]
]

Here:

Code
n = 3

2. Initialize the first row

Java
int prev0 = mat[0][0];
int prev1 = mat[0][1];
int prev2 = mat[0][2];

For the first row there is no previous row, so we can directly use its costs.

For:

Code
[1, 4, 1]

we get:

Code
prev0 = 1
prev1 = 4
prev2 = 1

3. Process every remaining row

Java
for (int i = 1; i < n; i++) {

We start from row 1 because row 0 has already been initialized.

4. Calculate the cost for Choice 0

Java
int curr0 = mat[i][0] + Math.min(prev1, prev2);

If we select Choice 0 in the current row, we cannot select Choice 0 in the previous row.

Therefore, we choose the cheaper of:

Code
previous Choice 1
previous Choice 2

5. Calculate the cost for Choice 1

Java
int curr1 = mat[i][1] + Math.min(prev0, prev2);

If the current row selects Choice 1, the previous row must use Choice 0 or Choice 2.

6. Calculate the cost for Choice 2

Java
int curr2 = mat[i][2] + Math.min(prev0, prev1);

If the current row selects Choice 2, the previous row must use Choice 0 or Choice 1.

Example Dry Run

Consider:

Code
mat = [
    [1, 4, 1],
    [3, 2, 2],
    [3, 2, 3]
]

First row

Code
prev0 = 1
prev1 = 4
prev2 = 1

So:

Code
prev = [1, 4, 1]

Second row

Current row:

Code
[3, 2, 2]

Calculate Choice 0:

Code
curr0 = 3 + min(4, 1)
      = 3 + 1
      = 4

Choice 1:

Code
curr1 = 2 + min(1, 1)
      = 2 + 1
      = 3

Choice 2:

Code
curr2 = 2 + min(1, 4)
      = 2 + 1
      = 3

Therefore:

Code
curr = [4, 3, 3]

Update:

Code
prev = [4, 3, 3]

Third row

Current row:

Code
[3, 2, 3]

Choice 0:

Code
curr0 = 3 + min(3, 3)
      = 6

Choice 1:

Code
curr1 = 2 + min(4, 3)
      = 5

Choice 2:

Code
curr2 = 3 + min(4, 3)
      = 6

Therefore:

Code
curr = [6, 5, 6]

Finally:

Code
answer = min(6, 5, 6)
       = 5

Why Does This Work?

The key observation is that when selecting a choice in the current row, only the choice selected in the immediately previous row matters.

For example, if we select Choice 1 now:

Code
Current → Choice 1

we only need to know the minimum cost of reaching the previous row using:

Code
Choice 0 OR Choice 2

We don't need to know the selections from earlier rows because their minimum costs are already included in prev0, prev1, and prev2.

This is the optimal substructure property of Dynamic Programming.

Why Not Use a 2D DP Array?

A traditional DP solution could use:

Java
dp[i][0]
dp[i][1]
dp[i][2]

for every row.

That would require:

Code
O(n) space

But we only need the previous row to calculate the current row.

Therefore, we can optimize:

Code
2D DP
    ↓
Previous row + Current row
    ↓
Only 3 previous values

So the space becomes:

Code
O(1)

Complexity Analysis

Time Complexity

We process every row exactly once.

For each row, we perform a constant number of operations.

Therefore:

Code
Time Complexity = O(n)

Space Complexity

We only use:

Java
prev0
prev1
prev2
curr0
curr1
curr2

The number of variables does not depend on n.

Therefore:

Code
Auxiliary Space = O(1)

Important Pattern to Remember

This problem follows a very common DP pattern:

Code
Current Choice 0
    → previous must be 1 or 2

Current Choice 1
    → previous must be 0 or 2

Current Choice 2
    → previous must be 0 or 1

The general formula is:

Code
curr0 = cost0 + min(prev1, prev2)
curr1 = cost1 + min(prev0, prev2)
curr2 = cost2 + min(prev0, prev1)

This pattern is useful for problems where you need to minimize cost while preventing the same state/choice from being selected consecutively.

Final Takeaway

The most important idea is:

For each choice in the current row, add its cost to the minimum cost of the two allowed choices from the previous row.

Because there are only 3 choices, we can calculate everything using a few variables and achieve the required:

Code
O(n) Time
O(1) Space

This makes the solution efficient even when n is as large as 100,000.