Easy Cpp Code
Intuition\n Describe your first thoughts on how to solve this problem. \nOnce you find the flaw in the question, the problem becomes easy.\n\n1. The child start
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nOnce you find the flaw in the question, the problem becomes easy.\n\n1. The child starting from (0, 0) must always move along the diagonal, since it needs to reach the target position of (n-1,n-1).\n2. The other two children never cross the diagonal, since they are supposed to reach the node (n-1, n-1).\n\nOnce you figure this out, its simple recursion - dp memoization.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(n^2)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n^2)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\nprivate:\n    int getTop( int i, int j, vector<vector<int>> &fruits, vector<vector<int>> &dp ) {\n        if( dp[i][j] != -1 ) return dp[i][j];\n        return dp[i][j] = fruits[i][j] + max( { getTop( i+1, j-1, fruits, dp ),\n                                                getTop( i+1, j, fruits, dp ),\n                                                getTop( i+1, j+1, fruits, dp ) } );\n    }\n    int getBottom( int i, int j, vector<vector<int>> &fruits, vector<vector<int>> &dp ) {\n        if( dp[i][j] != -1 ) return dp[i][j];\n        return dp[i][j] = fruits[i][j] + max( { getBottom( i-1, j+1, fruits, dp ),\n                                                getBottom( i, j+1, fruits, dp ),\n                                                getBottom( i+1, j+1, fruits, dp ) } );\n    }\npublic:\n    int maxCollectedFruits(vector<vector<int>>& fruits) {\n        int res = 0, n = fruits.size();\n        for( int i=0; i<n; i++ ) {\n            res += fruits[i][i];\n            fruits[i][i] = 0;\n        }\n        vector<vector<int>> dp1( n+1, vector<int>( n+1, 0 ) ), dp2( n+1, vector<int>( n+1, 0 ) );\n        for( int i=0; i<n; i++ ) {\n            for( int j=i+1; j<n; j++ ) {\n                dp1[i][j] = -1;\n                dp2[j][i] = -1;\n            }\n        }\n        return res + getTop( 0, n-1, fruits, dp1 ) + getBottom( n-1, 0, fruits, dp2 );\n    }\n};\n```
['C++']