Maximum Path Sum in a Grid with Specific Movement Constraints

Problem Statement

Maximum Path Sum in a Grid with Specific Movement Constraints Problem Description You are given a rectangular grid board with n rows and m columns. Rows are numbered 0 to n - 1 from top to bottom and columns 0 to m - 1 from left to right. A path visits exactly one cell in every row . It starts in one of two ways: Downward: start at cell (0, p) in the top row and move down one row at a time until you reach row n - 1 . Upward: start at cell (n - 1, q) in the bottom row and move up one row at a time until you reach row 0 . From a cell in column c , the next row's cell must be in column c - 1 , c or c + 1 (the cell directly below/above it, or one of its two diagonal neighbours). All moves must stay inside the grid; columns do not wrap around. The path may end in any column of the last row it reaches. The score of a path is the sum of the values of all the cells it visits. Return the maximum score over all downward paths that start at (0, p) and all upward paths that start at (n - 1, q) . I