Dynamic Programming on Grid to Maximize Valid Moves | Java | C++ | Video Solution
Intuition, approach, and complexity discussed in video solution in detail\nhttps://youtu.be/AbuXnJRpRYc\n# Code\njava []\nclass Solution {\n    public int maxMo
# Intuition, approach, and complexity discussed in video solution in detail\nhttps://youtu.be/AbuXnJRpRYc\n# Code\n```java []\nclass Solution {\n    public int maxMoves(int[][] grid) {\n        int rows = grid.length, cols = grid[0].length;\n        int[][] maxMovsAt = new int[rows][cols];\n        \n        for (int r = 0; r < rows; r++) {\n            maxMovsAt[r][0] = 1;\n        }\n\n        int maxMovs = 0;\n        for (int c = 1; c < cols; c++) {\n            for (int r = 0; r < rows; r++) {\n                int left = (grid[r][c - 1] < grid[r][c] && maxMovsAt[r][c - 1] > 0) \n                           ? maxMovsAt[r][c - 1] + 1 : 0;\n                int leftUpD = (r - 1 >= 0 && grid[r - 1][c - 1] < grid[r][c] && maxMovsAt[r - 1][c - 1] > 0) \n                              ? maxMovsAt[r - 1][c - 1] + 1 : 0;\n                int leftDownD = (r + 1 < rows && grid[r + 1][c - 1] < grid[r][c] && maxMovsAt[r + 1][c - 1] > 0) \n                                ? maxMovsAt[r + 1][c - 1] + 1 : 0;\n                \n                maxMovsAt[r][c] = Math.max(left, Math.max(leftUpD, leftDownD));\n                maxMovs = Math.max(maxMovs, maxMovsAt[r][c] - 1);\n            }\n        }\n\n        return maxMovs;\n    }\n}\n\n```\n``` C++ []\nclass Solution {\npublic:\n    int maxMoves(vector<vector<int>>& grid) {\n        int rows = grid.size(), cols = grid[0].size();\n        vector<vector<int>> maxMovsAt(rows, vector<int>(cols, 0));\n        \n        for (int r = 0; r < rows; r++) {\n            maxMovsAt[r][0] = 1;\n        }\n\n        int maxMovs = 0;\n        for (int c = 1; c < cols; c++) {\n            for (int r = 0; r < rows; r++) {\n                int left = (grid[r][c - 1] < grid[r][c] && maxMovsAt[r][c - 1] > 0) \n                           ? maxMovsAt[r][c - 1] + 1 : 0;\n                int leftUpD = (r - 1 >= 0 && grid[r - 1][c - 1] < grid[r][c] && maxMovsAt[r - 1][c - 1] > 0) \n                              ? maxMovsAt[r - 1][c - 1] + 1 : 0;\n                int leftDownD = (r + 1 < rows && grid[r + 1][c - 1] < grid[r][c] && maxMovsAt[r + 1][c - 1] > 0) \n                                ? maxMovsAt[r + 1][c - 1] + 1 : 0;\n                \n                maxMovsAt[r][c] = max(left, max(leftUpD, leftDownD));\n                maxMovs = max(maxMovs, maxMovsAt[r][c] - 1);\n            }\n        }\n\n        return maxMovs;\n    }\n};\n```
['Array', 'Dynamic Programming', 'Matrix', 'C++', 'Java']