Simple and understandable solution, calculating the right triangle and lower triangle using 2d DP
Intuition\n Describe your first thoughts on how to solve this problem. \nBecause the children are constrained to go n-1 steps, the range they can go is limited.
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nBecause the children are constrained to go `n-1` steps, the range they can go is limited.\n\nFor the child starting from the top-left corner, the only path is to directly go along the diagonal. Any other path can not reach the goal in `n-1` step. \n\nFor the child starting from the bottom-left corner, the reachable range is the lower triangle in the dungeon. As a result, we can build a 2d dp array for the lower triangle to calculate how many fruits can be collected.\n\nSimilar way happens for the child starting from the top-right corner. However, the reachable range is the right triangle in the dungeon instead. We can also use the 2d dp array to calculate the maximum fruits accessible in the right triangle\n\n![image.png](https://assets.leetcode.com/users/images/bece8d9e-ff1d-4b8a-bbab-97e41dd0ea21_1732379464.879988.png)\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\nFirstly, collect all of the fruits on the diagonal line and set the fruits on these cell as 0.\n\nSecondly, use a 2d array to calculate the maximum fruits collected in the lower triangle. We start from the bottom-left corner and go rightward. Then we add the dp solution in the goal, which means the fruits we can collect in the lower triangle.\n\nFinally, use a 2d array to calculate the maximum fruits collected in the right triangle. We start from the top-right corner and go downward. We add the dp solution in the goal, which means the fruits we can collect in the right triangle.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n  $$O(n)$$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int maxCollectedFruits(vector<vector<int>>& fr) {\n        int sol = 0;\n        int n = fr.size();\n\n        // all diagonal fruits can only be collected by the child starting from left top corner\n        for (int i = 0; i < n; i++) {\n            sol += fr[i][i];\n            fr[i][i] = 0;\n        }\n\n        // build the dp array\n        vector<vector<int>> dp(n, vector<int>(n, 0));\n\n        // collect by the child from bottom left corner\n        dp[n-1][0] = fr[n-1][0];\n        for (int j = 1; j <= n/2; j++) {\n            for (int i = n-1; i >= (n-1-j); i--) {\n                int op1 = (i-1 >= (n-1-j)+1)? fr[i][j] + dp[i-1][j-1] : 0;\n                int op2 = fr[i][j] + dp[i][j-1];\n                int op3 = (i+1 < n) ? fr[i][j] + dp[i+1][j-1] : 0;\n                dp[i][j] = max({op1, op2, op3});\n            }\n        }\n        for (int j = n/2 + 1; j < n; j++) {\n            for (int i = n-1; i >= j; i--) {\n                int op1 = fr[i][j] + dp[i-1][j-1];\n                int op2 = fr[i][j] + dp[i][j-1];\n                int op3 = (i+1 < n) ? fr[i][j] + dp[i+1][j-1] : 0;\n                dp[i][j] = max({op1, op2, op3});\n            }\n        }\n        sol += dp[n-1][n-1];\n        \n        // collect by the child from top right corner\n        dp[0][n-1] = fr[0][n-1];\n        for (int i = 1; i <= n/2; i++) {\n            for (int j = n-1; j >= (n-1-i); j--) {\n                int op1 = (j-1 >= (n-1-i)+1)? fr[i][j] + dp[i-1][j-1] : 0;\n                int op2 = fr[i][j] + dp[i-1][j];\n                int op3 = (j+1 < n) ? fr[i][j] + dp[i-1][j+1] : 0;\n                dp[i][j] = max({op1, op2, op3});\n            }\n        }\n        for (int i = n/2 + 1; i < n; i++) {\n            for (int j = n-1; j >= n-1-(n-1-i); j--) {\n                int op1 = fr[i][j] + dp[i-1][j-1];\n                int op2 = fr[i][j] + dp[i-1][j];\n                int op3 = (j+1 < n) ? fr[i][j] + dp[i-1][j+1] : 0;\n                dp[i][j] = max({op1, op2, op3});\n            }\n        }\n        sol += dp[n-1][n-1];\n       \n        return sol;\n    }\n};\n```
['C++']