Dp take both children independently
Intuition\nInitially i thought of doing it with 4d dp. But then i saw a pattern where row is always going into +1 state for bottom left cell and col is also goi
# Intuition\nInitially i thought of doing it with 4d dp. But then i saw a pattern where row is always going into +1 state for bottom left cell and col is also going into +1 state for top right cell. So i thought of doing it in 2d dp kind of way same as cherry pickup 2 problem.\nBut indeed it was wrong and i couldn\'t get correct answers in the contest.Afterwards i saw discuss section and it was a rather very simple problem because i had to consider both children move independently.\n\n\n# Approach\nApproach is quite simple here we have to ignore the top cell because it always has to move i+1,j+1 so we just add it to result simply at the beginning.\nNow the only tricky part was to recognize that we have to let the children play independently.\nSo we take two dp states and independently calculated both children maxpath and add all of it in the end simple.\n\nAlso to handle intersections just initially while calculating for the diagonal sum just take all the fruits i.e set fruits[i][i]=0.\n\n# Complexity\n- Time complexity:\n    O(n2)\n\n- Space complexity:\n    O(n2)\n\n# Code\n```cpp []\nclass Solution {\npublic:\n     long long cherryPickup1(int row,int col,vector<vector<int>>& grid\n    ,vector<vector<int>>&dp1){\n        \n        int n=grid.size();\n        if(col<0 ||  col>=n || row>=n ||row<0){\n            return -1e8;\n        }\n        if(row==n-1 && col==n-1){\n            return 0;\n        }\n        if(dp1[row][col]!=-1)return dp1[row][col];\n        \n        long long maxi=-1e8;\n        \n           for(int dj=-1;dj<=+1;dj++) {\n                long long value=0;\n                // if(row==nrow && col==ncol)value=grid[row][col]+\n                // cherryPickup(row+di,col+dj,nrow+1,ncol+1,grid,dp);\n                value=grid[row][col]+\n                cherryPickup1(row+dj,col+1,grid,dp1);\n                maxi=max(maxi,value);\n           }\n        \n        return dp1[row][col]=maxi;\n    }\n    long long cherryPickup2(int row,int col,vector<vector<int>>& grid\n    ,vector<vector<int>>&dp2){\n        \n        int n=grid.size();\n        if(col<0 ||  col>=n || row>=n ||row<0){\n            return -1e8;\n        }\n        if(row==n-1 && col==n-1){\n            return 0;\n        }\n        if(dp2[row][col]!=-1)return dp2[row][col];\n        \n        long long maxi=-1e8;\n        \n           for(int dj=-1;dj<=+1;dj++) {\n                long long value=0;\n                // if(row==nrow && col==ncol)value=grid[row][col]+\n                // cherryPickup(row+di,col+dj,nrow+1,ncol+1,grid,dp);\n                value=grid[row][col]+\n                cherryPickup2(row+1,col+dj,grid,dp2);\n                maxi=max(maxi,value);\n           }\n        \n        return dp2[row][col]=maxi;\n    }\n    int maxCollectedFruits(vector<vector<int>>& fruits) {\n        int col=fruits[0].size();\n        int row=fruits.size();\n        vector<vector<int>>dp1(row,vector<int>(col,-1));\n        vector<vector<int>>dp2(row,vector<int>(col,-1));\n        int result=0;\n        for(int i=0;i<row;i++){\n            for(int j=0;j<col;j++){\n                if(i==j){\n                    result+=fruits[i][j];\n                    fruits[i][i] = 0;\n                }\n            }\n        }\n        \n        int result1= (int)cherryPickup1(row-1,0,fruits,dp1);\n        int result2= (int)cherryPickup2(0,col-1,fruits,dp2);\n        \n        result+=result1+result2;\n        cout<<result<<endl;\n        \n        return result;\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'C++']