Minimum/Maximum Falling Path Sum
2D/3D DP and Grids DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Maximum Falling Path Sum in a Matrix (Variable Starting and Ending Points), Dynamic Programming, Memoization, Tabulation, Space Optimization, Matrices, Recursion, Time Complexity, Space Complexity, dynamic programming, memoization, tabulation, space optimization, matrix traversal, recursion, tree traversal, Grid / Matrix DP.
Maximum Falling Path Sum Problem Statement Given an N x M matrix, find the maximum path sum from any cell in the first row to any cell in the last row. From any cell (row, col), you can move to three possible cells in the next row: 1. Directly below: (row + 1, col) 2. Bottom right diagonal: (row + 1, col + 1) 3. Bottom left diagonal: (row + 1, col 1) You need to return the maximum path sum possible. Input Specification The first line contains two integers N and M, representing the number of rows and columns, respectively. The next N lines each contain M integers, representing the elements of the matrix. Output Specification Print a single integer, the maximum path sum. Constraints 1 <= N, M <= 100 10^9 <= matrix[i][j] <= 10^9 Sample Test Case Input: Output: