# LC 2684. Maximum Number of Moves in a Grid

### [Problem link](https://leetcode.com/problems/maximum-number-of-moves-in-a-grid/)

###### tags: `leedcode` `python` `medium` `DP`

You are given a **0-indexed** <code>m x n</code> matrix <code>grid</code> consisting of **positive** integers.

You can start at **any** cell in the first column of the matrix, and traverse the grid in the following way:

- From a cell <code>(row, col)</code>, you can move to any of the cells: <code>(row - 1, col + 1)</code>, <code>(row, col + 1)</code> and <code>(row + 1, col + 1)</code> such that the value of the cell you move to, should be **strictly** bigger than the value of the current cell.

Return the **maximum** number of **moves** that you can perform.

**Example 1:**
<img alt="" src="https://assets.leetcode.com/uploads/2023/04/11/yetgriddrawio-10.png" style="width: 201px; height: 201px;" />

Input: grid = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15]]
Output: 3
Explanation: We can start at the cell (0, 0) and make the following moves:
- (0, 0) -> (0, 1).
- (0, 1) -> (1, 2).
- (1, 2) -> (2, 3).
It can be shown that it is the maximum number of moves that can be made.

**Example 2:**

<img alt="" src="https://assets.leetcode.com/uploads/2023/04/12/yetgrid4drawio.png" />
Input: grid = [[3,2,4],[2,1,9],[1,1,7]]
Output: 0
Explanation: Starting from any cell in the first column we cannot perform any moves.

**Constraints:**

- <code>m == grid.length</code>
- <code>n == grid[i].length</code>
- <code>2 <= m, n <= 1000</code>
- <code>4 <= m * n <= 10⁵</code>
- <code>1 <= grid[i][j] <= 10⁶</code>

## Solution 1 - DP

class Solution:
    def maxMoves(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        dp = [[0 for _ in range(n)] for _ in range(m)]

        for j in range(n-2, -1, -1):
            for i in range(m):
                if 0 <= i - 1 < m and grid[i][j] < grid[i - 1][j + 1]:
                    dp[i][j] = max(dp[i][j], dp[i - 1][j + 1] + 1)
                if grid[i][j] < grid[i][j + 1]:
                    dp[i][j] = max(dp[i][j], dp[i][j + 1] + 1)
                if 0 <= i + 1 < m and grid[i][j] < grid[i + 1][j + 1]:
                    dp[i][j] = max(dp[i][j], dp[i + 1][j + 1] + 1)

        return max(list(zip(*dp))[0])

>### Complexity
>m = grid.length
>n = grid[i].length
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(mn) | O(mn) |

## Note
x