DP, O(n^2) with explanation and detailed comments
Observation\n Describe your first thoughts on how to solve this problem. \nThe child starting at (0,0) always moves diagonally to (i+1,i+1). This is the only wa
# Observation\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe child starting at (0,0) always moves diagonally to (i+1,i+1). This is the only way to reach (n\u22121,n\u22121) in n\u22121 steps.\n\nThe child starting at (n\u22121,0) cannot move further up than (n/2,i), as exceeding this limit would make it impossible to reach (n\u22121,n\u22121). \n\nSimilarly, the child starting at (0,n\u22121) cannot move further left than (0,n/2).\n\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Calculate the total number of fruits collected by the child starting at (0,0). After this, set all cells visited by this child to 0 for simplicity.\n2. For the child starting in the top-right corner:\nThe optimal strategy is to remain within the top-right section and avoid the diagonal (0,0)-(n\u22121,n\u22121), since no fruits remain there.\n\n    Furthermore, this child cannot cross the diagonal, as doing so would make it impossible to reach (n\u22121,n\u22121). Using dynamic programming (DP), calculate how many fruits this child can collect.\n\n3. Similarly, use DP to calculate how many fruits the child in the bottom-left corner can collect.\n4. Return the total number of fruits collected by the three children.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n^2)$$ for dp\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$ extra space for dp\n# Code\n```cpp []\nint maxCollectedFruits(vector<vector<int>>& grid) {\n    int ans = 0, n = grid.size();\n    for (int i = 0 ; i < n ; ++i) {\n        ans += grid[i][i];\n        grid[i][i] = 0;\n    }\n    \n    vector<int> dp1(n, -1), dp2(n, -1);\n\n    // Initialize dp1 for the bottom-left child starting at (n-1, 0)\n    dp1[n - 1] = grid[n - 1][0];\n\n    /*\n    dp1[x] represents the maximum number of fruits the child starting at (n-1, 0)\n    can collect when at position grid[x][col].\n\n    To reach grid[x][col], the child must have come from one of:\n    - grid[x-1][col-1] (diagonal up-left),\n    - grid[x][col-1] (straight left),\n    - grid[x+1][col-1] (diagonal down-left).\n\n    Thus, dp1[x] = max(prev[x-1], prev[x], prev[x+1]) + grid[x][col]\n    */\n    for (int col = 1; col < n; ++col) { // Process each column from left to right\n        auto prev = dp1; // Store the previous column\'s DP values\n        dp1.assign(n, -1); // Reset dp1 for the current column\n\n        for (int x = n / 2 + n % 2; x < n; ++x) { // Only consider valid rows in the bottom half\n            // Check all possible moves (up-left, left, down-left)\n            for (int dx = -1; dx <= 1; ++dx) {\n                int prevRow = x + dx;\n                if (prevRow < 0 || prevRow >= n || prev[prevRow] < 0) continue; // Skip invalid moves\n                dp1[x] = max(dp1[x], prev[prevRow] + grid[x][col]);\n            }\n        }\n    }\n\n    // Initialize dp2 for the top-right child starting at (0, n-1)\n    dp2[n - 1] = grid[0][n - 1];\n\n    /*\n    dp2[y] represents the maximum number of fruits the child starting at (0, n-1)\n    can collect when at position grid[row][y].\n\n    To reach grid[row][y], the child must have come from one of:\n    - grid[row-1][y-1] (diagonal up-left),\n    - grid[row][y-1] (straight left),\n    - grid[row+1][y-1] (diagonal down-left).\n\n    Thus, dp2[y] = max(prev[y-1], prev[y], prev[y+1]) + grid[row][y]\n    */\n    for (int row = 1; row < n; ++row) { // Process each row from top to bottom\n        auto prev = dp2; // Store the previous row\'s DP values\n        dp2.assign(n, -1); // Reset dp2 for the current row\n\n        for (int y = n / 2 + n % 2; y < n; ++y) { // Only consider valid columns in the top half\n            // Check all possible moves (up-left, up, up-right)\n            for (int dy = -1; dy <= 1; ++dy) {\n                int prevCol = y + dy;\n                if (prevCol < 0 || prevCol >= n || prev[prevCol] < 0) continue; // Skip invalid moves\n                dp2[y] = max(dp2[y], prev[prevCol] + grid[row][y]);\n            }\n        }\n    }\n    return ans + dp1.back() + dp2.back();\n}\n```
['C++']