Simple Generic DP solution for Grid problems.
Intuition\n Describe your first thoughts on how to solve this problem. \n1) reach destination in n - 1 moves.\n2) try all possible ways from start to end pick m
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n1) reach destination in n - 1 moves.\n2) try all possible ways from start to end pick max out of it.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nif we are starting from (0, 0) to reach (n - 1, n - 1) in n - 1 moves.\ndiagonal is the only way.\n\nsimilary we if startuing from (0  n - 1) & (n - 1, 0) to reach (n - 1, n - 1) in n - 1 moves. they will never intersect. \n\n# Complexity\n- Time complexity: \n<!-- Add your time complexity here, e.g. $$O(ROWS * COlS)$$ -->\n$$O(ROWS * COlS)$$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(ROWS * COlS)$$ \n# Code\n```java []\nclass Solution {\n    int[][] fruits;\n    int rows;\n    int cols;\n\n    int[][] directions1  = new int[][] {{1, -1}, {1, 0}, {1, 1}};\n    int[][] directions2 = new int[][] {{-1, 1}, {0, 1}, {1, 1}};\n\n    public int maxCollectedFruits(int[][] fruits) {\n        this.fruits = fruits;\n\n        rows = fruits.length;\n        cols = fruits[0].length;\n\n        int fruitsCollected = 0;\n\n        for (int row = 0; row < rows; row++) {\n            fruitsCollected += fruits[row][row]; // rows == cols\n            fruits[row][row] = 0;\n        }\n\n        Integer[][] dp1 = new Integer[rows][cols];\n        Integer[][] dp2 = new Integer[rows][cols];\n\n        return fruitsCollected + helper(0, rows - 1, directions1, dp1, 0) + helper(rows - 1, 0, directions2, dp2, 0);\n    }\n\n\n    int helper(int curRow, int curCol, int[][] directions, Integer[][] dp, int moves) {\n        if (curRow < 0 || curCol < 0 || curRow >= rows || curCol >= cols || moves >= rows) return Integer.MIN_VALUE;\n\n        if (moves == rows - 1) {\n            if (curRow == rows - 1 && curCol == cols - 1) return 0;\n            return Integer.MIN_VALUE;\n        }\n\n        if (dp[curRow][curCol] != null) return dp[curRow][curCol];\n\n        int maxFruits = Integer.MIN_VALUE;\n\n        for (int[] direction: directions) {\n            int nextRow = curRow + direction[0];\n            int nextCol = curCol + direction[1];\n\n            maxFruits = Math.max(maxFruits, fruits[curRow][curCol] + helper(nextRow, nextCol, directions, dp, 1 + moves));\n        }\n\n        return dp[curRow][curCol] = maxFruits;\n    }\n}\n```
['Math', 'Dynamic Programming', 'Java']