LeetCode 1810: Minimum Path Cost in a Hidden Grid

Explanation:

Given a hidden grid where each cell has a cost associated with it, find the minimum cost path from the start cell (0, 0) to the target cell (n-1, m-1). You can only move right or down from a cell.

To solve this problem, we can use dynamic programming. We will create a 2D DP array where dp[i][j] represents the minimum cost to reach cell (i, j) from the start cell.

1. Initialize the DP array with maximum values except for dp[0][0] which is the cost of the starting cell.
2. For each cell (i, j), the minimum cost to reach that cell is the minimum of the cost of reaching from the cell above (i-1, j) and the cell on the left (i, j-1) plus the cost of the current cell.
3. Finally, the value in dp[n-1][m-1] will be the minimum cost to reach the target cell.

:

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