Minimum Path Sum in Grid
2D/3D DP and Grids DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Minimum Path Sum in a Grid, Dynamic Programming, Recursion, Memoization, Tabulation, Space Optimization, Matrices, Grid Traversal, Time Complexity, Space Complexity, Greedy Algorithm, dynamic programming, memoization, tabulation, space optimization, recursion, greedy algorithm limitations, Greedy Algorithms.
Minimum Path Sum in a Grid Problem Statement Given an N x M matrix of integers, you need to find a path from the top left corner (0, 0) to the bottom right corner (N 1, M 1) such that the sum of all cell values along the path is minimized. At every cell, you can only move right or down. Input Specification The first line contains two integers N and M, representing the number of rows and columns of the matrix, respectively. The next N lines each contain M integers, representing the values of the cells in the matrix. Output Specification Print the minimum path sum. Constraints 1 <= N, M <= 200 0 <= matrix[i][j] <= 100 Sample Test Cases Input: Output: Explanation: The matrix is: Possible paths and their sums: (0,0) (0,1) (0,2) (1,2) : 5 + 9 + 6 + 2 = 22 (0,0) (0,1) (1,1) (1,2) : 5 + 9 + 5 + 2 = 21 (Minimum) (0,0) (1,0) (1,1) (1,2) : 5 + 11 + 5 + 2 = 23 The minimum path sum is 21.