Diagonal and 2 DFS
Code\ncpp []\nclass Solution {\n    // DFS for the child starting from (n-1, 0)\n    int dfs1(vector<vector<int>>& fruits, int i, int j, vector<vector<int>>& dp
# Code\n```cpp []\nclass Solution {\n    // DFS for the child starting from (n-1, 0)\n    int dfs1(vector<vector<int>>& fruits, int i, int j, vector<vector<int>>& dp) {\n        int n = fruits.size();\n\n        // Base case: If we reach the destination (n-1, n-1)\n        if (i == n - 1 && j == n - 1)\n            return 0;\n\n        // Invalid state: The current column index (j) must be less than the row index (i)\n        if (j >= i)\n            return 0;\n\n        // Use memoized result if available\n        if (dp[i][j] != -1)\n            return dp[i][j];\n\n        int maxFruits = 0;\n\n        // Explore all possible moves for the child\n        for (int d = -1, ii = i - 1; d <= 1; ++d, ++ii) {\n            if (ii >= 0 && ii < n)  // Ensure the move is within bounds\n                maxFruits = max(maxFruits, dfs1(fruits, ii, j + 1, dp));\n        }\n\n        // Store and return the maximum fruits collected from this point\n        return dp[i][j] = maxFruits + fruits[i][j];\n    }\n\n    // DFS for the child starting from (0, n-1)\n    int dfs2(vector<vector<int>>& fruits, int i, int j, vector<vector<int>>& dp) {\n        int n = fruits.size();\n\n        // Base case: If we reach the destination (n-1, n-1)\n        if (i == n - 1 && j == n - 1)\n            return 0;\n\n        // Invalid state: The current row index (i) must be less than the column index (j)\n        if (i >= j)\n            return 0;\n\n        // Use memoized result if available\n        if (dp[i][j] != -1)\n            return dp[i][j];\n\n        int maxFruits = 0;\n\n        // Explore all possible moves for the child\n        for (int d = -1, jj = j - 1; d <= 1; ++d, ++jj) {\n            if (jj >= 0 && jj < n)  // Ensure the move is within bounds\n                maxFruits = max(maxFruits, dfs2(fruits, i + 1, jj, dp));\n        }\n\n        // Store and return the maximum fruits collected from this point\n        return dp[i][j] = maxFruits + fruits[i][j];\n    }\n\npublic:\n    int maxCollectedFruits(vector<vector<int>>& fruits) {\n        int n = fruits.size();\n        int totalFruits = 0;\n\n        // Collect fruits from the diagonal path (0, 0) -> (n-1, n-1)\n        for (int i = 0; i < n; ++i)\n            totalFruits += fruits[i][i];\n\n        // Create DP tables for the two additional children\n        vector<vector<int>> dp1(n, vector<int>(n, -1));  // For child starting at (n-1, 0)\n        vector<vector<int>> dp2(n, vector<int>(n, -1));  // For child starting at (0, n-1)\n\n        // Add maximum fruits collected by the two children\n        totalFruits += dfs1(fruits, n - 1, 0, dp1);  // Child 1 (from (n-1, 0))\n        totalFruits += dfs2(fruits, 0, n - 1, dp2);  // Child 2 (from (0, n-1))\n\n        return totalFruits;\n    }\n};\n\n```
['C++']