[Java/C++/Python] DP, first child go diagonal
Intuition\nFirst child will go along the diagonal.\n\n\n# Explanation\nFor first child,\ncollect fruits A[i][i] on the diagonal\n\nFor second child,\nA[i][j] +=
# **Intuition**\nFirst child will go along the diagonal.\n<br>\n\n# **Explanation**\nFor first child,\ncollect fruits `A[i][i]` on the diagonal\n\nFor second child,\n`A[i][j] += max(dp[i - 1][j - 1], A[i - 1][j], A[i - 1][j + 1])`\n\nFor third child,\n`A[i][j] += max(A[i - 1][j - 1], A[i][j - 1], A[i + 1][j - 1] )`\n<br>\n\n# **Complexity**\nTime `O(n^2)`\nSpace `O(n)`\n<br>\n\n```Java [Java]\n    public int maxCollectedFruits(int[][] A) {\n        int n = A.length;\n        // Set inaccessible cells to 0\n        for (int i = 0; i < n; ++i) {\n            for (int j = 0; j < n; ++j) {\n                if (i < j && j < n - 1 - i) {\n                    A[i][j] = 0;\n                }\n                if (j < i && i < n - 1 - j) {\n                    A[i][j] = 0;\n                }\n            }\n        }\n\n        // First child\n        int res = 0;\n        for (int i = 0; i < n; ++i) {\n            res += A[i][i];\n        }\n\n        // Second child\n        for (int i = 1; i < n; ++i) {\n            for (int j = i + 1; j < n; ++j) {\n                A[i][j] += Math.max(A[i - 1][j - 1],\n                                  Math.max(A[i - 1][j], (j + 1 < n) ? A[i - 1][j + 1] : 0));\n            }\n        }\n\n        // Third child\n        for (int j = 1; j < n; ++j) {\n            for (int i = j + 1; i < n; ++i) {\n                A[i][j] += Math.max(A[i - 1][j - 1],\n                                  Math.max(A[i][j - 1], (i + 1 < n) ? A[i + 1][j - 1] : 0));\n            }\n        }\n\n        return res + A[n - 1][n - 2] + A[n - 2][n - 1];\n    }\n```\n\n```C++ [C++]\n    int maxCollectedFruits(vector<vector<int>>& A) {\n        int n = A.size();\n        // Set inaccessible cells to 0\n        for (int i = 0; i < n; ++i) {\n            for (int j = 0; j < n; ++j) {\n                if (i < j && j < n - 1 - i) {\n                    A[i][j] = 0;\n                }\n                if (j < i && i < n - 1 - j) {\n                    A[i][j] = 0;\n                }\n            }\n        }\n        // First child\n        int res = 0;\n        for (int i = 0; i < n; ++i) {\n            res += A[i][i];\n        }\n        // Second child\n        for (int i = 1; i < n; ++i) {\n            for (int j = i + 1; j < n; ++j) {\n                A[i][j] += max({A[i - 1][j - 1], A[i - 1][j], (j + 1 < n) ? A[i - 1][j + 1] : 0});\n            }\n        }\n        // Thrid child\n        for (int j = 1; j < n; ++j) {\n            for (int i = j + 1; i < n; ++i) {\n                A[i][j] += max({A[i - 1][j - 1], A[i][j - 1], (i + 1 < n) ? A[i + 1][j - 1] : 0});\n            }\n        }\n        return res + A[n - 1][n - 2] + A[n - 2][n - 1];;\n    }\n```\n\n```py [Python3]\n    def maxCollectedFruits(self, A: List[List[int]]) -> int:\n        n = len(A)\n        for i in range(n):\n            for j in range(n):\n                if i < j < n - 1 - i:\n                    A[i][j] = 0\n                if j < i < n - 1 - j:\n                    A[i][j] = 0\n        for i in range(1, n):\n            for j in range(i + 1, n):\n                A[i][j] += max(A[i - 1][j - 1], A[i - 1][j], A[i - 1][j + 1] if j + 1 < n else 0)\n        for j in range(1, n):\n            for i in range(j + 1, n):\n                A[i][j] += max(A[i - 1][j - 1], A[i][j - 1], A[i + 1][j - 1] if i + 1 < n else 0)\n        return sum(A[i][i] for i in range(n)) + A[-1][-2] + A[-2][-1]\n```\n\n# More DP problems\nHere is small DP problem list.\nGood luck and have fun.\n- 3363. [Find the Maximum Number of Fruits Collected](https://leetcode.com/problems/find-the-maximum-number-of-fruits-collected/discuss/6075890/JavaC%2B%2BPython-First-child-go-diagonal)\n- 3352. [Count K-Reducible Numbers Less Than N](https://leetcode.com/problems/count-k-reducible-numbers-less-than-n/discuss/6028638/JavaC%2B%2BPython-DP)\n- 3351. [Sum of Good Subsequences](https://leetcode.com/problems/sum-of-good-subsequences/discuss/6028686/JavaC%2B%2BPython-DP)\n- 3336. [Find the Number of Subsequences With Equal GCD](https://leetcode.com/problems/find-the-number-of-subsequences-with-equal-gcd/discuss/5973616/JavaC%2B%2BPython-2D-DP)\n- 3335. [Total Characters in String After Transformations I](https://leetcode.com/problems/total-characters-in-string-after-transformations-i/discuss/5973021/Python-DP)\n- 3316. [Find Maximum Removals From Source String](https://leetcode.com/problems/find-maximum-removals-from-source-string/discuss/5904277/JavaC%2B%2BPython-DP)\n- 3202. [Find the Maximum Length of Valid Subsequence II](https://leetcode.com/problems/find-the-maximum-length-of-valid-subsequence-ii/discuss/5389350/JavaC%2B%2BPython-1d-DP)\n- 3193. [Count the Number of Inversions](https://leetcode.com/problems/count-the-number-of-inversions/discuss/5353127/Python-DP)\n- 3177. [Find the Maximum Length of a Good Subsequence II](https://leetcode.com/problems/find-the-maximum-length-of-a-good-subsequence-ii/discuss/5280172/JavaC%2B%2BPython-DP-Solution)\n- 3148. [Maximum Difference Score in a Grid](https://leetcode.com/problems/maximum-difference-score-in-a-grid/discuss/5145704/JavaC%2B%2BPython-Minimum-on-Top-Left)\n- 3147. [Taking Maximum Energy From the Mystic Dungeon](https://leetcode.com/problems/taking-maximum-energy-from-the-mystic-dungeon/discuss/5145723/JavaC%2B%2BPython-DP)\n- 2920. [Maximum Points After Collecting Coins From All Nodes](https://leetcode.com/problems/maximum-points-after-collecting-coins-from-all-nodes/discuss/4220643/JavaC%2B%2BPython-DP)\n- 2919. [Minimum Increment Operations to Make Array Beautiful](https://leetcode.com/problems/minimum-increment-operations-to-make-array-beautiful/discuss/4220717/JavaC%2B%2BPython-Easy-and-Concise-DP-O(1)-Space)\n- 2896. [Apply Operations to Make Two Strings Equal](https://leetcode.com/problems/apply-operations-to-make-two-strings-equal/discuss/4144041/JavaC%2B%2BPython-DP-One-Pass-O(1)-Space)\n- 2830. [Maximize the Profit as the Salesman](https://leetcode.com/problems/maximize-the-profit-as-the-salesman/discuss/3934188/JavaC%2B%2BPython-DP)\n- 2008. [Maximum Earnings From Taxi](https://leetcode.com/problems/maximum-earnings-from-taxi/discuss/1470941/JavaC%2B%2BPython-DP-solution)\n- 1751. [Maximum Number of Events That Can Be Attended II](https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended-ii/discuss/1052581/Python-DP)\n- 1235. [Maximum Profit in Job Scheduling](https://leetcode.com/problems/maximum-profit-in-job-scheduling/discuss/409009/Python-DP-Solution)\n
['C', 'Python', 'Java']