SIMPLE AND EASY DP SOLUTION IN CPP WITH EASY VISUALIZATION.
Intuition\nFirst for child at (0,0) there is only a possible path which is the diagonal.\nFor child at (n-1,0) the path will be below diagonals.\nFor child at (
# Intuition\nFirst for child at (0,0) there is only a possible path which is the diagonal.\nFor child at (n-1,0) the path will be below diagonals.\nFor child at (0,n-1) the path will be above diagonals.\n\n# Approach\nFirst traverse the diagonals and add it to count this will make sure that (0,0) reaches the end.\nCreate a matrix where the other 2 childs can traverse.\nFor example: if n=5\nThe matrix would be of the form:\n1 1 1 1 0\n1 1 1 0 0\n1 1 1 0 0\n1 0 0 1 0\n0 0 0 0 1\nit means the child at (n-1,0) can traverse only through zeroes and another condition is only 3 right neighbours.\nSimilarly, the child at (0,n-1) can traverse only through zeroes and another condition is only 3 down neighbours.\n\nNow start from (n-1,1) and see the maximum of left 3 which are,\nfor (i,j) see for (i-1,j-1), (i,j-1), (i+1,j-1) and continue till (n-1,n-2).\nSimilarly, start from (1,n-1) and see the maximum of above 3 which are, for (i,j) see for (i-1,j-1), (i-1,j), (i-1,j+1) and continue till (n-1,n-2). \n\nDuring iteration break when u encounter a 1.\n\nThe final count will be summation of child at (0,0) and fruits value at (n-1,n-2) and fruits value at (n-2,n-1).\n\n\n# Complexity\n- Time complexity:\nO(N^2)\n\n- Space complexity:\nO(N^2)\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int maxCollectedFruits(vector<vector<int>>& fruits) {\n        \n        int n = fruits.size(), count = 0;\n\n        if(n==2)\n        return fruits[0][0]+fruits[0][1]+fruits[1][0]+fruits[1][1];\n\n        vector<vector<int>> matrix(n, vector<int>(n, 0));\n        for (int i=0;i<n-1;i++) \n        for (int j=0;j<n-i-1;j++) \n        matrix[i][j]=1;\n\n        for (int i=0;i<n;i++) \n        {\n            count+=fruits[i][i];\n            fruits[i][i]=0;\n            matrix[i][i]=1;\n        }\n\n        int a,b,c,i,j;  \n\n        for (i=1;i<n-1;i++) {\n            j=n-1;\n            while(matrix[i][j]==0) {  \n                a = 0, b = 0, c = 0;\n                if(matrix[i-1][j-1]==0) a=fruits[i-1][j-1];\n                if(matrix[i-1][j]==0) b=fruits[i-1][j];\n                if(j+1<=n-1 && matrix[i-1][j+1]==0) c=fruits[i-1][j+1];\n                fruits[i][j]+=max({a, b, c});\n                j--;\n            }\n        }\n\n        for (j=1;j<n-1;j++) {  \n            i=n-1;\n            while(matrix[i][j]==0) {  \n                a = 0, b = 0, c = 0;\n                if(matrix[i-1][j-1]==0) a=fruits[i-1][j-1];\n                if(matrix[i][j-1]==0) b=fruits[i][j-1];\n                if(i+1<=n-1 && matrix[i+1][j-1]==0) c=fruits[i+1][j-1];\n                fruits[i][j]+=max({a, b, c});\n                i--;\n            }\n        }\n\n        count+=fruits[n-1][n-2]+fruits[n-2][n-1];\n\n        return count;\n    }\n};\n\n```
['C++']