DP Memoisation || C++
Intuition\nThe (0,0) child will always follow the diagonal.\nThe (0,n-1) & (n-1,0) child wont\'t cross or touch the diagonal.\nNow just use DP on subsequences w
# Intuition\nThe (0,0) child will always follow the diagonal.\nThe (0,n-1) & (n-1,0) child wont\'t cross or touch the diagonal.\nNow just use DP on subsequences with this condition and move the two children.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Complexity\n- Time complexity: O(n*n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n*n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int dp1[1001][1001];\n    int dp2[1001][1001];\n    int n;\n    int f(int x,int y,vector<vector<int>>& arr){\n        if(x == n-2 && y == n-1) return arr[x][y];\n        if(dp1[x][y] != -1) return dp1[x][y];\n        int ans = arr[x][y];\n        int take1 = 0,take2 = 0,take3 = 0;\n        if(x+1 < n && y+1 <n && x+1 < y+1){\n            take1 = f(x+1,y+1,arr);\n        }\n        if(x+1 < n && x+1 < y){\n            take2 = f(x+1,y,arr);\n        }\n        if(x+1 < n && y-1 >= 0 && x+1 < y-1){\n            take3 = f(x+1,y-1,arr);\n        }\n        ans += max({take1,take2,take3});\n        return dp1[x][y] = ans;\n    }\n\n    int _f(int x,int y,vector<vector<int>>& arr){\n        if(x == n-2 && y == n-1) return arr[x][y];\n        if(dp2[x][y] != -1) return dp2[x][y];\n        int ans = arr[x][y];\n        int take1 = 0,take2 = 0,take3 = 0;\n        if(x+1 < n && y+1 <n && x+1 > y+1){\n            take1 = _f(x+1,y+1,arr);\n        }\n        if(y+1 < n && x > y+1){\n            take2 = _f(x,y+1,arr);\n        }\n        if(x-1 >= 0 && y+1 < n && x-1 > y+1){\n            take3 = _f(x-1,y+1,arr);\n        }\n        ans += max({take1,take2,take3});\n        return dp2[x][y] = ans;\n    }    \n\n    int maxCollectedFruits(vector<vector<int>>& fruits) {\n        n = fruits.size();\n        memset(dp1,-1,sizeof(dp1));\n        memset(dp2,-1,sizeof(dp2));\n        int ans1 = f(0,n-1,fruits);\n        int ans2 = _f(n-1,0,fruits);\n        int ans3 = 0;\n        for(int i=0; i<n; i++) ans3 += fruits[i][i];\n        return ans1 + ans2 + ans3;\n    }\n};\n```
['Dynamic Programming', 'Memoization', 'C++']