LeetCode 2304: Minimum Path Cost in a Grid Solution

Master LeetCode problem 2304 (Minimum Path Cost in a Grid), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2304. Minimum Path Cost in a Grid

Medium

Array Dynamic Programming Matrix

Problem Explanation

Explanation

To solve this problem, we can use dynamic programming to find the minimum cost of a path from the first row to the last row in the given grid. We will iterate row by row and calculate the minimum cost to reach each cell in the current row based on the minimum cost of reaching the cells in the previous row.

We will maintain a 2D array to store the minimum cost to reach each cell. At each cell, the minimum cost will be the sum of the value of the cell in the grid and the minimum cost to reach that cell from the cells in the previous row, considering the moving costs.

After iterating through all rows, the minimum cost to reach any cell in the last row will be our final answer.

Algorithm:

Initialize a 2D array dp of size m x n to store the minimum cost to reach each cell.
Fill the first row of dp with the values from the first row of the grid.
Iterate over each row starting from the second row:
- For each cell in the current row, calculate the minimum cost to reach that cell based on the minimum cost of reaching the cells in the previous row.
- Update the dp array with the minimum cost for each cell.
Find the minimum cost in the last row of dp, which will be the minimum cost of a path from the first row to the last row.

Time Complexity:

The time complexity of this algorithm is O(m * n) where m is the number of rows and n is the number of columns in the grid.

Space Complexity:

The space complexity is also O(m * n) as we are using a 2D array to store the minimum costs.

Solution Code

class Solution {
    public int minPathCost(int[][] grid, int[][] moveCost) {
        int m = grid.length;
        int n = grid[0].length;
        
        int[][] dp = new int[m][n];
        for (int j = 0; j < n; j++) {
            dp[0][j] = grid[0][j];
        }
        
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = grid[i][j] + dp[i-1][0] + moveCost[grid[i-1][0]][j];
                for (int k = 1; k < n; k++) {
                    dp[i][j] = Math.min(dp[i][j], grid[i][j] + dp[i-1][k] + moveCost[grid[i-1][k]][j]);
                }
            }
        }
        
        int minCost = Integer.MAX_VALUE;
        for (int j = 0; j < n; j++) {
            minCost = Math.min(minCost, dp[m-1][j]);
        }
        
        return minCost;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2304 (Minimum Path Cost in a Grid)?

This page provides optimized solutions for LeetCode problem 2304 (Minimum Path Cost in a Grid) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2304 (Minimum Path Cost in a Grid)?

The time complexity for LeetCode 2304 (Minimum Path Cost in a Grid) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2304 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2304 in Java, C++, or Python.

Back to LeetCode Solutions