No DP. just brute
Intuition\n Describe your first thoughts on how to solve this problem. \n\n\nIt is given kids tavel n-1 steps. This is the key.\n\nFor topleft kid to travel n-1
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n![{AEAB2D33-BAD4-4FE4-9625-0CED35199C06}.png](https://assets.leetcode.com/users/images/3a85f810-975e-406f-831a-a27b24c60c1f_1732447555.5224118.png)\n\nIt is given kids tavel n-1 steps. This is the key.\n\nFor topleft kid to travel n-1 steps on n*n grid, there is only one way to reach bottom right. i.e. to travel from topleft to bottom right\n\nFor Bottom left kid, max deviation it can take is given in image (Red). kid can deviate max by this much only. All paths of kid lies inside this triangle , so calculate and store max along the way\n\nSame for TopRight kid, max deviation it can take is given in iamge(Green). for this too calculate max fruits it can take bound by this max freedom.\n\nFollowing diagram tells the range of paths of kids (line denotes max deviation they can take)\n\nFor n=9\n![{281DE334-5EA3-4349-9C24-801A0B62C883}.png](https://assets.leetcode.com/users/images/86711ac8-7b79-4e07-8e87-d913161568c2_1732447253.5308673.png)\n\nFor n=10\n![{7AD722DC-DDC2-42F6-805D-6E60D5CEDD84}.png](https://assets.leetcode.com/users/images/e5c5c969-919d-4f9a-a2ed-8f12e2fd8f84_1732447147.9343941.png)\n\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```javascript []\n/**\n * @param {number[][]} fruits\n * @return {number}\n */\nvar maxCollectedFruits = function(fruits) {\n    let n = fruits.length;\n    let totalsum = 0, half = Math.ceil( (n-1) / 2);\n    //top left goes diagonically to bottom right\n    for(let i=0; i<n; i++) {\n        totalsum += fruits[i][i];\n    }\n    //bottom left triangle\n    function updateFromLeftPaths(i,j) {\n        let maxFromLeft = 0;\n        if (i-1 >= n - j) {\n            maxFromLeft = fruits[i-1][j - 1];\n        }\n        if (i >= n - j) {\n            maxFromLeft = Math.max(maxFromLeft, fruits[i][j-1]);\n        }\n        if (i+1 >= n - j && i+1 < n) {\n            maxFromLeft = Math.max(maxFromLeft, fruits[i+1][j-1]);\n        }\n        fruits[i][j] += maxFromLeft;\n    }\n    for(let j=1; j<=half - 1; j++) {\n        for(let i=n - 1; i>= n - j - 1; i--) {\n            updateFromLeftPaths(i,j);\n        }\n    }\n    for(let j=half; j<=n - 2; j++) {\n        for(let i=n - 1; i>= j + 1; i--) {\n            updateFromLeftPaths(i,j);\n        }\n    }\n    //fruits[n-1][n-2] has max for topLeftKid\n    totalsum += fruits[n - 1][n - 2];\n\n    //top right\n    function updateFromTopPaths(i,j) {\n        let maxFromTop = 0;\n        if (j-1 >= n - i) {\n            maxFromTop = fruits[i-1][j-1];\n        }\n        if (j >= n - i) {\n            maxFromTop = Math.max(maxFromTop, fruits[i-1][j]);\n        }\n        if (j+1 >= n - i && j+1 < n) {\n            maxFromTop = Math.max(maxFromTop, fruits[i-1][j+1]);\n        }\n        fruits[i][j] += maxFromTop;\n    }\n    for(let i=1; i<=half - 1; i++) {\n        for(let j=n - 1; j>= n - i - 1; j--) {\n            updateFromTopPaths(i,j);\n        }\n    }\n    for(let i=half; i<=n - 2; i++) {\n        for(let j=n - 1; j>= i + 1; j--) {\n            updateFromTopPaths(i,j);\n        }\n    }\n    //fruits[n-2][n-1] has totalfruits for topright kid\n    totalsum += fruits[n - 2][n - 1];\n    return totalsum;\n};\n```
['JavaScript']