🌱 Keegan's Digital Garden

2304. Minimum Path Cost in a Grid

3 min read

📝 Problem Details

💭What Were My Initial Thoughts?

- the grid make things seem different but this is essentially a graph question where nodes (elements in the matrix) have connected edges that are weighted (per the moveCost vector) 

- could explicitly construct a graph via an adjacency list out of these values, and then conduct dijkstras shortest path, returning the minCost of this path

🤔What Did I Struggle With?

- explicitly constructing a graph would be inefficient
	- need a way of constructing the minCost without constructing a graph 
	- there is *something in the question that should allow us to do this*

- in a traditional graph, each node has the ability to connect to any other node in the graph
- this question outlines the rule that a node can only connect to nodes in the next row of the grid
	- this means we can break the problem down into subproblems
	  where the solution for row i is dependent only on row i - 1

💡 Explanation of Solution

the minimum cost to reach any cell in the grid depends only on:
	1. the minimum cost to reach the previous row's cell
	2. the cost of moving to the current cell

you can build the solution **incrementally** by solving smaller subproblems (minimum cost to reach each cell in the current row) - therefore we dont need to care about the actual path itself

Approach:
1. define the state:
	- dp[i][j] = minimum cost to reach cell (i,j) in the grid 

2. transition
	- To compute dp[i][j, consider all cells (i-1, k) in the previous row:
	- where k is the min cost of cells in the previous row
	- dp[i][j] = min(dp[i][j], dp[i-1][k] + moveCost[grid[i-1][k]][j] + grid[i][j])

3. base case
	- for the first row, dp[0][j] = grid[0][j]

4. result:
	- the minimum cost to traverse the grid is:
	- min(dp[lastrow][j])

⌛ Complexity Analysis

Time Complexity: O(m*n^2)

Space Complexity: O(m*n)

💻 Implementation of Solution

/*
    - m*n matrix
    - integers in the matrix are unique
    - you can move from a cell to any other cell in the next row (within bounds)
    - you cannot move from cells in the last row 
    - each move has a cost (found in moveCost matrix)
        - moveCost[i][j] is the cost of moving from cell with value i --> to cell in column j of the next row
        - ignore the cost of moving from cells in the last row 
 
 
*/
class Solution {
public:
    int minPathCost(vector<vector<int>>& grid, vector<vector<int>>& moveCost) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, INT_MAX));
 
        // base case : first row
        for(int j=0; j < n; j++)
            dp[0][j] = grid[0][j];
        
        // fill the dp array
        for(int i=1; i < m; i++) {      // iterate through the rows, starting at the second row
            for(int j=0; j < n; j++) {  // iterate through each cell in row i
                for(int k=0; k < n; k++) {  // check all cells in the previous row
                    dp[i][j] = min(dp[i][j], dp[i-1][k] + moveCost[grid[i-1][k]][j] + grid[i][j]);
                }
            }
        }
 
        // get the minCost from the min element in the last row of dp
        return *min_element(dp[m - 1].begin(), dp[m - 1].end());
    }
};

Graph View