DP solution C++
Intuition\n Describe your first thoughts on how to solve this problem. \nHint is in the no. of moves.\n# Approach\n Describe your approach to solving the proble
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nHint is in the no. of moves.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nChild1 (0,0) can only move along the diagonal\nChild2 and Child3 can move only in lower half and right half of the matrix. Their region of traveral make a triangle.\nSo split the 2D-DP matrix calculation into two phases for each child.\nRest is straight-forward DP.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n^2)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n^2)\n# Code\n```cpp []\nclass Solution {\npublic:\n    int maxCollectedFruits(vector<vector<int>>& fruits) {\n        int n = fruits.size();\n        \n        int total = 0;\n        for(int i=0;i<n;i++) {\n            total += fruits[i][i];\n            fruits[i][i] = 0;\n        }\n        if(n==2) {\n            return total + fruits[0][1] + fruits[1][0];\n        }\n        \n        vector<vector<int>> child1(n, vector<int>(n, 0));\n        child1[n-1][0] = fruits[n-1][0];\n        for(int j=1; j<=(n-1)/2; j++) {\n            for(int i=n-1; i+j>=n-1; i--) {\n                int maxval = 0;\n                if(i+1 < n && j-1>=0)\n                    maxval = max(maxval, child1[i+1][j-1]);\n                if(j-1>=0)\n                    maxval = max(maxval, child1[i][j-1]);\n                if(i-1>=0 && j-1>=0)\n                    maxval = max(maxval, child1[i-1][j-1]);\n                child1[i][j] = fruits[i][j] + maxval;\n            }\n        }\n        for(int j=(n+1)/2; j<n;j++) {\n            for(int i=(n)/2+1; i < n ;i++) {\n                int maxval = 0;\n                if(i+1 < n && j-1>=0)\n                    maxval = max(maxval, child1[i+1][j-1]);\n                if(j-1>=0)\n                    maxval = max(maxval, child1[i][j-1]);\n                if(i-1>=0 && j-1>=0)\n                    maxval = max(maxval, child1[i-1][j-1]);\n                child1[i][j] = fruits[i][j] + maxval;\n            }\n        }\n\n        \n        total += child1[n-1][n-1];\n        \n        vector<vector<int>> child2(n, vector<int>(n, 0));\n        child2[0][n-1] = fruits[0][n-1];\n        for(int i=1; i<=(n-1)/2; i++) {\n            for(int j = n-1; i+j>=n-1; j--) {\n                \n                int maxval = 0;\n                if(i-1>=0)\n                    maxval = max(maxval, child2[i-1][j]);\n                if(i-1>=0 && j-1>=0)\n                    maxval = max(maxval, child2[i-1][j-1]);\n                if(i-1>=0 && j+1<n)\n                    maxval = max(maxval, child2[i-1][j+1]);\n                child2[i][j] = fruits[i][j] + maxval;\n            }\n        }\n        \n        for(int i=(n+1)/2; i<n; i++) {\n            for(int j=(n)/2+1; j<n;j++) {\n                \n                int maxval = 0;\n                if(i-1>=0)\n                    maxval = max(maxval, child2[i-1][j]);\n                if(i-1>=0 && j-1>=0)\n                    maxval = max(maxval, child2[i-1][j-1]);\n                if(i-1>=0 && j+1<n)\n                    maxval = max(maxval, child2[i-1][j+1]);\n                child2[i][j] = fruits[i][j] + maxval;\n            }\n        }\n\n        total += child2[n-1][n-1];\n        return total;\n    }\n};\n```
['Dynamic Programming', 'C++']