DFS | Recursion | Dynamic Programming | Memoization
Intuition\n Describe your first thoughts on how to solve this problem. \n Problem is referecnce of finding max score from starting position ( 0 , 0 ) to reach t
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n* Problem is referecnce of finding max score from starting position `( 0 , 0 )` to reach the end `(n-1, n-1)` of the matrix.\n* But in this problem, we need to find max scores from three different corners to reach the end `(n-1, n-1)`, and sum up the max scores which are obtained from three individual paths `( 0 , 0 )`, `( 0 , n-1 )` and `( n-1 , 0 )`.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. find the maximum fruits for each child using recursion.\n2. sum up the evary child score to get answers.\n\n# Complexity\n- Time complexity: $$O(2^n)$$\n<!-- Add your time complexity here, e.g. $$O(2^n)$$ -->\n\n- Space complexity: $$O( stack space + n^2 )$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    int n;\n    int[][] dp;\n    int[][] grid;\n    public int maxCollectedFruits(int[][] grid) {\n        this.n = grid.length;\n        this.grid = grid;\n        this.dp = new int[n][n];\n\n        for(int[] is : dp) Arrays.fill(is,-1);\n        // first child\n        int firstChildScore = collectFromFirstChild();\n\n        // Second child\n        int secondChildScore = dfsSecondChild(0,n-1);\n\n        // Third Child\n        int thirdChildScore = dfsThirdChild(n-1,0);\n\n        return (firstChildScore + secondChildScore + thirdChildScore);\n    }\n\n    public int dfsSecondChild(int i,int j) {\n        \n        if (i < 0 || i >= n || j < 0 || j >= n) {\n            return 0;\n        }\n        if (i == n-1 && j == n-1) {\n            return 0;\n        }\n        if ( i == j || i > j) {\n            return 0;\n        }\n       \n        if(dp[i][j]  != -1) return dp[i][j];\n\n        int leftcorner = grid[i][j] + dfsSecondChild(i+1, j-1);\n        int middle = grid[i][j] + dfsSecondChild( i+1, j);\n        int rightcorner = grid[i][j] + dfsSecondChild(i+1, j+1);\n\n        return dp[i][j] = Math.max(middle, Math.max(rightcorner,leftcorner));\n    }\n\n    public int dfsThirdChild(int i,int j) {\n        \n        if (i < 0 || i >= n || j < 0 || j >= n) {\n            return 0;\n        }\n        if (i == n-1 && j == n-1) {\n            return 0;\n        }\n        if ( i == j || j > i) {\n            return 0;\n        }\n        if(dp[i][j] != -1) return dp[i][j];\n\n        int topcorner = grid[i][j] + dfsThirdChild( i-1, j+1);\n        int right = grid[i][j] + dfsThirdChild( i, j+1);\n        int rightcorner = grid[i][j] + dfsThirdChild(i+1, j+1);\n\n        return dp[i][j] = Math.max(right, Math.max(rightcorner,topcorner));\n    }\n\n    public int collectFromFirstChild() {\n        int ans = 0;\n        for (int i = 0; i < n; i++) {\n            ans += grid[i][i];\n            grid[i][i] = 0;\n            dp[i][i] = 0;\n        }\n        return ans;\n    }\n}\n```
['Dynamic Programming', 'Depth-First Search', 'Recursion', 'Memoization', 'Java']