---
# System prepended metadata

title: LC 2684. Maximum Number of Moves in a Grid
tags: [medium, leedcode, DP, python]

---

# 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<sup>5</sup></code>
- <code>1 <= grid[i][j] <= 10<sup>6</sup></code>


## Solution 1 - DP
```python=
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
