Simple DP, three children are independent, O(n*n)
Intuition\n Describe your first thoughts on how to solve this problem. \nThe thing is that for the child start at (0, 0), he can only go to (i + 1, j + 1) from 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe thing is that for the child start at (0, 0), he can only go to (i + 1, j + 1) from (i, j).\nFor the child start at(n - 1, 0), he cannot cross the line of "i = j", or they have no time to turn back to (n - 1, n - 1).\nSo as the third child start at (0, n - 1).\nThus, three child are indepent actually.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nFirst child go a straight line to (n - 1, n - 1).\nBottom left child take a DP for the bottom left part of the fruits.\nSo as top right\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n, n)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int n;\n    vector<vector<int>> fruits;\n    int dp1[1001][1001], dp2[1001][1001];\n    int maxCollectedFruits(vector<vector<int>>& fruits) {\n        n = fruits.size();\n        this->fruits = fruits;\n        int total = 0;\n        for (int i = 0; i < n; i++){\n            total += fruits[i][i];\n        }\n        cout << total << \'\\n\';\n        memset(dp1, -1, sizeof(dp1));\n        memset(dp2, -1, sizeof(dp2));\n        total += find1(n - 1, 0);\n        total += find2(0, n - 1);\n        return total;\n    }\n    int find1(int i, int j){\n        \n        if (i == n - 1 && j == n - 1)\n            return 0;\n        if (j >= i)\n            return 0;\n        if (dp1[i][j] != -1)\n            return dp1[i][j];\n        int maxV = 0;\n        int total = fruits[i][j];\n        if (i - 1 >= 0)\n            maxV = max(maxV, total + find1(i - 1, j + 1));\n        maxV = max(maxV, total + find1(i, j + 1));\n        if (i + 1 < n)\n            maxV = max(maxV, total + find1(i + 1, j + 1));\n        dp1[i][j] = maxV;\n        return maxV;\n    }\n    int find2(int i, int j){\n        \n        if (i == n - 1 && j == n - 1)\n            return 0;\n        if (i >= j)\n            return 0;\n        if (dp2[i][j] != -1)\n            return dp2[i][j];\n        int maxV = 0;\n        int total = fruits[i][j];\n        if (j - 1 >= 0)\n            maxV = max(maxV, total + find2(i + 1, j - 1));\n        maxV = max(maxV, total + find2(i + 1, j));\n        if (j + 1 < n)\n            maxV = max(maxV, total + find2(i + 1, j + 1));\n        dp2[i][j] = maxV;\n        return maxV;\n    }\n};\n```
['C++']