C++ Solution || DP || Recursion -> Memoization -> DP
C++:\n\n1). Recursion will give TLE :\n\nclass Solution {\npublic:\n    int helper(int n, int m, int row, int col, int val, vector<vector<int>>& grid) {\n\t\n\t
**C++:**\n\n**1). Recursion will give TLE :**\n```\nclass Solution {\npublic:\n    int helper(int n, int m, int row, int col, int val, vector<vector<int>>& grid) {\n\t\n\t\t//base case\n        if (col == m - 1) {\n            return 0;\n        }\n        \n        int rightupp = 0;\n        int right = 0;\n        int rightlow = 0;\n\t\t\n\t\t//condition check and recursion call with adding 1\n        if (row - 1 >= 0 && col + 1 < m && val < grid[row-1][col+1]) {\n            rightupp = 1 + helper(n, m, row-1, col+1, grid[row-1][col+1], grid);\n        }\n        if (row < n && col + 1 < m && val < grid[row][col+1]) {\n            right = 1 + helper(n, m, row, col+1, grid[row][col+1], grid);\n        }\n        if (row + 1 < n && col + 1 < m && val < grid[row+1][col+1]) {\n            rightlow = 1 + helper(n, m, row+1, col+1, grid[row+1][col+1], grid);\n        }\n        \n\t\t//return answer\n        return max(rightupp, max(right, rightlow));\n    }\n    \n    int maxMoves(vector<vector<int>>& grid) {\n        int n = grid.size();\n        int m = grid[0].size();\n        int maxi = 0;\n\t\t\n\t\t//checking for every starting position in first column\n        for (int i = 0; i < n; i++) {\n            maxi = max(maxi, helper(n, m, i, 0, grid[i][0], grid));\n        }\n\t\t\n        return maxi;\n    }\n};\n```\n\n**2). Memoization will give TLE :**\n```\nclass Solution {\npublic:\n    \n    int helper(int n,int m,int row,int col,int val,vector<vector<int>>& grid,vector<vector<int>> &dp){        \n        if(row<n && col==m-1){\n            return 0;\n        }     \n\t\t\n        if(dp[row][col]!=-1){\n            return dp[row][col];\n        }\n        \n        int rightupp=0;\n        int right=0;\n        int rightlow=0;\n        if(row-1>=0 && col+1<m && val<grid[row-1][col+1]){\n            rightupp=1+helper(n,m,row-1,col+1,grid[row-1][col+1],grid,dp);\n        }\n        if(row<n && col+1<m && val<grid[row][col+1]){\n            right=1+helper(n,m,row,col+1,grid[row][col+1],grid,dp);\n        }\n        if(row+1<n && col+1<m && val<grid[row+1][col+1]){\n            rightlow=1+helper(n,m,row+1,col+1,grid[row+1][col+1],grid,dp);\n        }\n\t\t\n        return dp[row][col]=max(rightupp,max(right,rightlow));\n        \n    }\n    \n    int maxMoves(vector<vector<int>>& grid) {\n        int n=grid.size();\n        int m=grid[0].size();\n        int maxi=0;\n\t\t\n\t\t//memoization vector \n        vector<vector<int>> dp(n,vector<int> (m,-1));\n\t\n        for(int i=0;i<n;i++){\n           maxi=max(maxi, helper(n,m,i,0,grid[i][0],grid,dp));\n        }\n        return maxi;\n    }\n};\n```\n\n**3). DP will get accepted :**\n```\nclass Solution {\npublic:\n    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        int ans = 0;\n        \n        for (int i = 0; i < n; i++) {\n            dp[i][m-1] = 0;\n        }\n        \n        for (int j = m-2; j >= 0; j--) {\n            for (int i = 0; i < n; i++) {\n                int rightupp = 0, right = 0, rightlow = 0;\n                int val = grid[i][j];\n                if (i-1 >= 0 && j+1 < m && val < grid[i-1][j+1]) {\n                    rightupp = 1 + dp[i-1][j+1];\n                }\n                if (j+1 < m && val < grid[i][j+1]) {\n                    right = 1 + dp[i][j+1];\n                }\n                if (i+1 < n && j+1 < m && val < grid[i+1][j+1]) {\n                    rightlow = 1 + dp[i+1][j+1];\n                }\n                dp[i][j] = max(rightupp, max(right, rightlow));\n            }\n        }\n        for (int i = 0; i < n; i++) {\n            ans = max(ans, dp[i][0]);\n        }\n\n        return ans;\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'C']