[C++, Java, Python3] Top Down DP
\n# Intuition\nGiven the constraints we can try a dynamic programming approach if each state is O(1). \n\n# Approach\n From each cell we will try to move to (i 
\n# Intuition\nGiven the constraints we can try a dynamic programming approach if each state is O(1). \n\n# Approach\n* From each cell we will try to move to (i + 1, j + 1) or (i, j + 1) or (i - 1, j + 1) if the values at these cells is greater than the current cell\n* We will try starting from all the cells in the first column `(i, 0)` where i is in `[0, m)`\n* Cache each state to avoid redundant calculations\n\n# Complexity\n- Time complexity: O(mn)\n\n- Space complexity: O(mn)\n\n# Code\n**Python3**:\n```\ndef maxMoves(self, grid: List[List[int]]) -> int:\n    m, n, dirs = len(grid), len(grid[0]), [(0, 1), (1, 1), (-1, 1)]\n    @cache\n    def dp(i, j):\n        ans = 0\n        for x, y in dirs:\n            ni, nj = i + x, j + y\n            if 0 <= ni < m and nj < n and grid[i][j] < grid[ni][nj]:\n                ans = max(ans, 1 + dp(ni, nj))\n        return ans\n    return max(dp(i, 0) for i in range(m))\n```\n\n**C++**:\n```\nint maxMoves(vector<vector<int>>& grid) {\n    int m = grid.size(), n = grid[0].size();\n    vector<pair<int, int>> dirs = {{0, 1}, {1, 1}, {-1, 1}};\n    vector<vector<int>> cache(m, vector<int>(n, -1));\n\n    function<int(int, int)> dp = [&](int i, int j) {\n        if (cache[i][j] != -1) return cache[i][j];\n        int ans = 0;\n        for (auto [x, y] : dirs) {\n            int ni = i + x, nj = j + y;\n            if (ni >= 0 && ni < m && nj < n && grid[i][j] < grid[ni][nj])\n                ans = max(ans, 1 + dp(ni, nj));\n        }\n        return cache[i][j] = ans;\n    };\n    int res = 0;\n    for (int i = 0; i < m; i++)\n        res = max(res, dp(i, 0));\n    return res;\n}\n```\n\n**Java**:\n```\nclass Solution {\n    int dirs[][] = {{0, 1}, {1, 1}, {-1, 1}}, m, n, cache[][];\n    public int maxMoves(int[][] grid) {\n        m = grid.length; n = grid[0].length; cache = new int[m][n];\n        Arrays.stream(cache).forEach(row -> Arrays.fill(row, -1));\n\n        int res = 0;\n        for (int i = 0; i < m; i++)\n            res = Math.max(res, dp(grid, i, 0));\n        return res;\n    }\n    \n    private int dp(int[][] grid, int i, int j) {\n        if (cache[i][j] != -1) return cache[i][j];\n        int ans = 0;\n        for (int[] dir : dirs) {\n            int ni = i + dir[0], nj = j + dir[1];\n            if (ni >= 0 && ni < m && nj < n && grid[i][j] < grid[ni][nj])\n                ans = Math.max(ans, 1 + dp(grid, ni, nj));\n        }\n        return cache[i][j] = ans;\n    }\n}\n```
['C++', 'Java', 'Python3']