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

<p>You can start at <strong>any</strong> cell in the first column of the matrix, and traverse the grid in the following way:</p>

<ul>
	<li>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 <strong>strictly</strong> bigger than the value of the current cell.</li>
</ul>

<p>Return <em>the <strong>maximum</strong> number of <strong>moves</strong> that you can perform.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2023/04/11/yetgriddrawio-10.png" style="width: 201px; height: 201px;" />
<pre>
<strong>Input:</strong> grid = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15]]
<strong>Output:</strong> 3
<strong>Explanation:</strong> We can start at the cell (0, 0) and make the following moves:
- (0, 0) -&gt; (0, 1).
- (0, 1) -&gt; (1, 2).
- (1, 2) -&gt; (2, 3).
It can be shown that it is the maximum number of moves that can be made.</pre>

<p><strong class="example">Example 2:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>2 &lt;= m, n &lt;= 1000</code></li>
	<li><code>4 &lt;= m * n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= grid[i][j] &lt;= 10<sup>6</sup></code></li>
</ul>

class Solution:
    def maxMoves(self, grid: List[List[int]]) -> int:

        # this problem is very easy the only tricky thing is the array is sideways

        # at each index starting from the very right side of the array, 
        # we need to keep track of how many moves each cell can make
        # starting from each cell, how far right can we go

        # our dp array will mimick the size of the grid, each row, col in dp will be 
        # the max moves we can make at row, col in grid
        # technically we are only ever going to look at the very next column in dp ever
        # so dp does not have to be the size of grid it can be just the size a column in dp
        # but whatever

        # this solution is linear, O(m * n)
        # however many items are in the grid so grid rows * grid cols

        dp = []
        cols = [0] * len(grid[0])

        for row in range(len(grid)):
            dp.append(cols[:])

        
        # iterating from the second last column (last column is already at the end of grid)
        # we will work our way down in each column from top row to bottom
        # checking every move that the cell can make to the right

        # iterate through columns second last to first
        for col in range(len(grid[0]) - 2, -1, -1):

            # iterate down the column (top row to bottom row in each column)
            for row in range(len(grid)):

                # print("value")
                # print(grid[row][col])
                
                # we need to check if there are any valid moves from cell

                # middle right position
                middle_right = grid[row][col + 1]

                # top right position (make sure inbounds)
                top_right = float("-inf") if row - 1 < 0 else grid[row - 1][col + 1]

                # bottom right position (make sure inbounds)
                bottom_right = float("-inf") if row + 1 >= len(grid) else grid[row + 1][col + 1]

                # keep track of the best move we come across
                # best move will be a valid move which has highest dp value
                # which is max number of moves forward we can make
                best = 0

                # keep track if there is even a possible move we can make
                possible = 0

                # make sure the values in the valid moves are greater than current value
                if top_right != float("-inf") and top_right > grid[row][col]:
                    best = max(best, dp[row - 1][col + 1])
                    possible = 1

                if middle_right > grid[row][col]:
                    best = max(best, dp[row][col + 1])
                    possible = 1

                if bottom_right != float("-inf") and bottom_right > grid[row][col]:
                    best = max(best, dp[row + 1][col + 1])
                    possible = 1
                

                # out of all the moves which are valid (inbound moves to the right of current cell
                # and values to the right are greater than value in current cell)
                # we want to select the cell to move to which has the greatest reach to the right
                # of the grid (has the highest value in dp)

                # if there are no valid moves then we need to change dp to 0 because at 
                # that cell there is no way we can move forward

                # at this cell what is the most amount of moves forward we can make
                dp[row][col] = best + possible
                

        # the farthest we can travel from any cell in the first column is the max
        # value in our dp first column
        maximum = 0
        # iterate through each row in first column
        for row in range(len(dp)):

            maximum = max(maximum, dp[row][0])
        
        # print(dp)
        return maximum
        
1333