Min Cost Path Problem
Problem Statement
Given a 2D cost matrix of size m x n and a starting position (0, 0), find the minimum cost path to reach (m-1, n-1). From any cell, you can move right, down, or diagonally (down-right).
Example:
- Input:
cost = [
[1, 2, 3],
[4, 8, 2],
[1, 5, 3]
]
- Output:
8(Path: 1 → 2 → 2 → 3 = 8)
Noob-Friendly Explanation
Imagine you're on a grid-shaped game board. Each square has a toll (cost) you must pay to step on it. You start at the top-left corner and want to reach the bottom-right corner. You can only move right, down, or diagonally. You want to find the cheapest route. It's like finding the cheapest path through a maze where each step costs money.
Approach 1: Brute Force
Intuition
From each cell, explore all three possible moves (right, down, diagonal). Recursively find the minimum cost path. This explores all possible paths.
Algorithm
- Start from
(0, 0). - At each cell, recursively try going right, down, and diagonal.
- Return the cost of the current cell plus the minimum of the three recursive calls.
- Base case: when we reach
(m-1, n-1), return its cost.
class Solution {
public static int minCostBrute(int[][] cost, int i, int j, int m, int n) {
// Base case: reached destination
if (i == m - 1 && j == n - 1) return cost[i][j];
// Out of bounds
if (i >= m || j >= n) return Integer.MAX_VALUE;
// Try all three directions
int right = minCostBrute(cost, i, j + 1, m, n);
int down = minCostBrute(cost, i + 1, j, m, n);
int diagonal = minCostBrute(cost, i + 1, j + 1, m, n);
return cost[i][j] + Math.min(right, Math.min(down, diagonal));
}
public static void main(String[] args) {
int[][] cost = {
{1, 2, 3},
{4, 8, 2},
{1, 5, 3}
};
System.out.println(minCostBrute(cost, 0, 0, 3, 3)); // Output: 8
}
}Complexity Analysis
- Time Complexity: O(3^(m+n)) - three choices at each cell, path length up to m+n
- Space Complexity: O(m + n) - recursion stack depth
Approach 2: Optimal
Intuition
Use a 2D DP table where dp[i][j] is the minimum cost to reach cell (i, j) from (0, 0). Each cell can be reached from the left, above, or diagonally above-left.
Algorithm
- Create a
dpmatrix of sizem x n. dp[0][0] = cost[0][0].- Fill the first row (can only come from the left) and first column (can only come from above).
- For all other cells:
dp[i][j] = cost[i][j] + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]). - Return
dp[m-1][n-1].
class Solution {
public static int minCostPath(int[][] cost) {
int m = cost.length;
int n = cost[0].length;
int[][] dp = new int[m][n];
dp[0][0] = cost[0][0];
// Fill first row
for (int j = 1; j < n; j++) {
dp[0][j] = dp[0][j - 1] + cost[0][j];
}
// Fill first column
for (int i = 1; i < m; i++) {
dp[i][0] = dp[i - 1][0] + cost[i][0];
}
// Fill rest of the table
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = cost[i][j] + Math.min(dp[i - 1][j],
Math.min(dp[i][j - 1], dp[i - 1][j - 1]));
}
}
return dp[m - 1][n - 1];
}
public static void main(String[] args) {
int[][] cost = {
{1, 2, 3},
{4, 8, 2},
{1, 5, 3}
};
System.out.println(minCostPath(cost)); // Output: 8
}
}Complexity Analysis
- Time Complexity: O(m * n) - we visit each cell once
- Space Complexity: O(m * n) - the dp matrix