DP recursion with memo->iterative tabular->prunig||3ms 95.65%
Intuition\n Describe your first thoughts on how to solve this problem. \n2D DP recursion with memo->iterative tabular\n\nTo speed up, pruning version is also pr
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n2D DP recursion with memo->iterative tabular\n\nTo speed up, pruning version is also provided, thanks to suggestion of @Sergei.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. n=len(matrix), m=len(matrix[0]) different from the LC\'s convention, but for the matrix convention\n2. `dp` is 2D state matrix; because of constraints `4 <= m * n <= 10^5` it\'s better to use dynamical allocation, not static array\n3. Define the recursive function `dp[i][j]=f(int i, int j, int prev, vector<vector<int>>& grid)` to compute the `dp`\n4. In `nt maxMoves(vector<vector<int>>& grid)` use a loop to compute `ans=max(ans, f(i, 0, -1, grid))` for i=0,...,n-1\n5. ans-1 is the answer, subtracting 1 as per initial setup\n6. An iterative DP version is also made.\n7.  Thanks to @Sergei, pruning version is made.\n8. Iteration with optimized space $O(n)$ is made using `&1` trick with j index.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(nm)$$ \n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(nm)$$ \n# Code Recursion+ memo 18ms||Pruning Early stop version 3ms 95.65%\n```C++ []\n//Pruning Early stop version 3ms 95.65%\nclass Solution {\npublic:\n    vector<vector<int>> dp;\n    int n, m;\n    int f(int i, int j, int prev, vector<vector<int>>& grid){\n        if (i<0 || j<0 ||i>=n || j>=m) return 0;\n        int x=grid[i][j];\n        if (x<=prev) return 0;\n        if(dp[i][j]!=-1) return dp[i][j];\n        int max_move=1+f(i-1, j+1, x, grid);\n        for (int i0=i; i0<=i+1; i0++){\n            if (max_move==m-j) break;// early stop pruning\n            max_move=max(max_move, 1+f(i0, j+1, x, grid));\n        }\n        return dp[i][j]=max_move;\n    }\n    int maxMoves(vector<vector<int>>& grid) {\n        n=grid.size(), m=grid[0].size();\n        dp.assign(n, vector<int>(m, -1));\n        int ans=0;\n        for (int i=0; i<n; i++){\n            if (ans==m) break;// early stop\n            ans=max(ans, f(i, 0, -1, grid));\n        }\n        return ans-1;\n    }\n};\n\n\nauto init = []()\n{ \n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```\n```cpp []\n// normal recursion+memo\nclass Solution {\npublic:\n    vector<vector<int>> dp;\n    int n, m;\n    int f(int i, int j, int prev, vector<vector<int>>& grid){\n        if (i<0 || j<0 ||i>=n || j>=m) return 0;\n        int x=grid[i][j];\n        if (x<=prev) return 0;\n        if(dp[i][j]!=-1) return dp[i][j];\n        \n        return dp[i][j]=1+max({f(i-1, j+1, x, grid),\n         f(i, j+1, x, grid),\n         f(i+1, j+1, x, grid)});\n    }\n    int maxMoves(vector<vector<int>>& grid) {\n        n=grid.size(), m=grid[0].size();\n        dp.assign(n, vector<int>(m, -1));\n        int ans=0;\n        for (int i=0; i<n; i++)\n            ans=max(ans, f(i, 0, -1, grid));\n        return ans-1;\n    }\n};\n\n\nauto init = []()\n{ \n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```\n# C++ iterative DP\n```\nclass Solution {\npublic:\n    static int maxMoves(vector<vector<int>>& grid) {\n        int n = grid.size(), m = grid[0].size();\n        vector<vector<int>> dp(n, vector<int>(m, 0));\n\n        // Initialize the last column to 1\n        for (int i = 0; i < n; i++)\n            dp[i][m - 1] = 1;\n\n        // Process from the second last column to the 0th\n        for (int j = m - 2; j >= 0; j--) {\n            for (int i = 0; i < n; i++) {\n                int x = grid[i][j];\n\n                // Check the cell E\n                int max_move = (x < grid[i][j + 1]) * dp[i][j + 1];\n\n                // Check the cell NE\n                if (i > 0 && x < grid[i - 1][j + 1])\n                    max_move = max(max_move, dp[i - 1][j + 1]);\n\n                // Check the cell SE\n                if (i < n - 1 && x < grid[i + 1][j + 1])\n                    max_move = max(max_move, dp[i + 1][j + 1]);\n\n                dp[i][j] = 1 + max_move;\n            }\n        }\n\n        // Calculate the maximum moves\n        int ans = 0;\n        for (int i = 0; i < n; i++)\n            ans = max(ans, dp[i][0]);\n\n        return ans - 1; // subtracting 1 as per initial setup\n    }\n};\n\nauto init = []() {\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```\n# C++ with optimized space\n```\nclass Solution {\npublic:\n    static int maxMoves(vector<vector<int>>& grid) {\n        const int n = grid.size(), m = grid[0].size();\n        int dp[1000][2];\n        memset(dp, 0, sizeof(dp));\n\n        // Initialize the last column to 1\n        for (int i = 0; i < n; i++)\n            dp[i][(m-1)&1] = 1;\n\n        // Process from the second last column to the 0th\n        for (int j = m-2; j >= 0; j--) {\n            for (int i=0; i < n; i++) {\n                int x=grid[i][j];\n\n                // Check the cell E\n                int max_move = (x < grid[i][j+1])?dp[i][(j+1)&1]:0;\n                \n                // Check the cell NE\n                if (max_move<m-j && i > 0 && x < grid[i-1][j+1])\n                    max_move = max(max_move, dp[i-1][(j+1)&1]);\n                \n                // Check the cell SE\n                if (max_move<m-j && i < n-1 && x < grid[i+1][j+1])\n                    max_move = max(max_move, dp[i+1][(j+1)&1]);\n\n                dp[i][j&1]=1+max_move;\n            }\n        }\n\n        // Calculate the maximum moves\n        int ans = 0;\n        for (int i = 0; i < n; i++){\n            if (ans==m) break;// early stop\n            ans=max(ans, dp[i][0]);\n        }\n\n        return ans-1; // subtracting 1 as per initial setup\n    }\n};\n\nauto init = []() {\n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```
['Array', 'Dynamic Programming', 'Matrix', 'C++']