Prerequisites: Matrix, Basic DP.
Problem:
Given an N x M matrix with non-negative integers, the task is to find the minimum sum of path cells from the top-left cell to the bottom-right cell. You can only move right or downward from any cell without exiting the matrix boundary.
Solution Approach:
The main idea is to use dynamic programming( why?, because this problem has both optimal substructure and overlapping subproblems) to efficiently find the minimum sum of path cells from the top-left cell to the bottom-right cell in the given matrix. We initialize a dynamic programming (DP) matrix of the same size as the input matrix and populate it iteratively. By traversing through the DP matrix, we compute the minimum sum for each cell by considering the minimum sum from the cell above and the cell to the left, and adding the value of the current cell from the input matrix. This approach effectively builds the solution bottom-up, ensuring that each cell contains the minimum sum of the path from the top-left cell to that cell. Finally, the value stored in the bottom-right cell of the DP matrix represents the minimum sum of path cells.
Time Complexity: O(N * M), as we iterate through all cells of the matrix once to compute the minimum sum.
Space Complexity: O(N * M) for the DP matrix, as it stores state information about each cell.