CPP | Memoization
\n# Code\ncpp []\nclass Solution {\npublic:\n    vector<vector<int>> fruits;\n    int n;\n    int dp2[1001][1001];\n    int dp3[1001][1001];\n\n    int g2(int x
\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<vector<int>> fruits;\n    int n;\n    int dp2[1001][1001];\n    int dp3[1001][1001];\n\n    int g2(int x, int y) {\n        if (x < 0 or x >= n or y < 0 or y >= n) {\n            return -INT_MAX;\n        }\n\n        if (x == n - 1 and y == n - 1) {\n            return fruits[x][y];\n        }\n\n        if (dp2[x][y] != -1) {\n            return dp2[x][y];\n        }\n\n        int result = fruits[x][y] + \n        max({\n            g2(x + 1, y - 1),\n            g2(x + 1, y),\n            g2(x + 1, y + 1)\n        });\n\n        return dp2[x][y] = result;\n    }\n\n\n    int g3(int x, int y) {\n        if (x < 0 or x >= n or y < 0 or y >= n) {\n            return -INT_MAX;\n        }\n\n        if (y == n - 1 and x == n - 1) {\n            return fruits[x][y];\n        }\n\n        if (dp3[x][y] != -1) {\n            return dp3[x][y];\n        }\n\n        int result = fruits[x][y] + \n        max({\n            g3(x - 1, y + 1),\n            g3(x, y + 1),\n            g3(x + 1, y + 1)\n        });\n\n        return dp3[x][y] = result;\n    }\n    int maxCollectedFruits(vector<vector<int>>& mat) {\n        this -> fruits = mat;\n        this -> n = fruits.size();\n        \n        int first_child = 0;\n        for (int i = 0; i < n; ++i) {\n            first_child += fruits[i][i];\n            fruits[i][i] = 0;\n        }\n\n        memset(dp2, -1, sizeof(dp2));\n        memset(dp3, -1, sizeof(dp3));\n        return first_child + g2(0, n - 1) + g3(n - 1, 0);\n    }\n};\n```
['Memoization', 'C++']