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:
mat = [
[1, 4, 1],
[3, 2, 2],
[3, 2, 3]
]
One optimal selection is:
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:
[10, 20, 30]
There are three choices:
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:
Choice 1 or Choice 2
So the minimum cost for choosing Choice 0 becomes:
current cost + minimum(previous choice 1, previous choice 2)
Similarly:
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:
prev0
prev1
prev2
They represent:
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
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
int n = mat.length;
n stores the total number of rows.
For example:
mat = [
[1, 4, 1],
[3, 2, 2],
[3, 2, 3]
]
Here:
n = 3
2. Initialize the first row
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:
[1, 4, 1]
we get:
prev0 = 1
prev1 = 4
prev2 = 1
3. Process every remaining row
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
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:
previous Choice 1
previous Choice 2
5. Calculate the cost for Choice 1
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
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:
mat = [
[1, 4, 1],
[3, 2, 2],
[3, 2, 3]
]
First row
prev0 = 1
prev1 = 4
prev2 = 1
So:
prev = [1, 4, 1]
Second row
Current row:
[3, 2, 2]
Calculate Choice 0:
curr0 = 3 + min(4, 1)
= 3 + 1
= 4
Choice 1:
curr1 = 2 + min(1, 1)
= 2 + 1
= 3
Choice 2:
curr2 = 2 + min(1, 4)
= 2 + 1
= 3
Therefore:
curr = [4, 3, 3]
Update:
prev = [4, 3, 3]
Third row
Current row:
[3, 2, 3]
Choice 0:
curr0 = 3 + min(3, 3)
= 6
Choice 1:
curr1 = 2 + min(4, 3)
= 5
Choice 2:
curr2 = 3 + min(4, 3)
= 6
Therefore:
curr = [6, 5, 6]
Finally:
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:
Current → Choice 1
we only need to know the minimum cost of reaching the previous row using:
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:
dp[i][0]
dp[i][1]
dp[i][2]
for every row.
That would require:
O(n) space
But we only need the previous row to calculate the current row.
Therefore, we can optimize:
2D DP
↓
Previous row + Current row
↓
Only 3 previous values
So the space becomes:
O(1)
Complexity Analysis
Time Complexity
We process every row exactly once.
For each row, we perform a constant number of operations.
Therefore:
Time Complexity = O(n)
Space Complexity
We only use:
prev0
prev1
prev2
curr0
curr1
curr2
The number of variables does not depend on n.
Therefore:
Auxiliary Space = O(1)
Important Pattern to Remember
This problem follows a very common DP pattern:
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:
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:
O(n) Time
O(1) Space
This makes the solution efficient even when n is as large as 100,000.