Easy C++ Solution
Intuition\nIf you notice carefull you\'ll see that the child starting at (0, 0) can only move diagonally as he has to reach the corner in n-1 moves which is onl
# Intuition\nIf you notice carefull you\'ll see that the child starting at (0, 0) can only move diagonally as he has to reach the corner in n-1 moves which is only possible this way, similarly as no child will want to go to room which another child already passed both the other child will move in theright and bottom region of a square formed by 2 diagonals.\nThen we use dp to compute max sum in both left and bottom region of square, please refer the code.\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int maxCollectedFruits(vector<vector<int>>& f) {\n        int n = f.size(), m = f[0].size();\n        vector dp(n, vector<int>(m, 0));\n        dp[0][m-1] = f[0][m-1];\n        for(int i = 1; i<n-1; i++)\n            {\n                for(int j = max(m-1-i, i+1); j<m; j++)\n                    {\n                        dp[i][j] = f[i][j];\n                        int x = 0;\n                        x = dp[i-1][j];\n                        if(j>0)\n                            x = max(x, dp[i-1][j-1]);\n                        if(j<m-1)\n                            x = max(x, dp[i-1][j+1]);\n                        \n                        dp[i][j] += x;    \n                    }\n            }\n        dp[n-1][0] = f[n-1][0];\n\n        for(int j = 1; j<m; j++)\n        {\n            for(int i = max(n-1-j, j+1); i<n; i++)\n            {\n                dp[i][j] = f[i][j];\n                int x = 0;\n                x = dp[i][j-1];\n                if(i>0)\n                    x = max(x, dp[i-1][j-1]);\n                if(i<n-1)\n                    x = max(x, dp[i+1][j-1]);\n                \n                dp[i][j] += x;\n            }  \n        }\n        long long ans = 0;\n        for(int i = 0; i<n; i++)\n                ans += f[i][i];\n        ans += dp[n-2][m-1];\n        ans += dp[n-1][m-2];\n\n        return ans;\n    }\n};\n```
['Dynamic Programming', 'C++']