C++ DP速解難題leetcode 3363 Find the Maximum Number of Fruits Collected/Py3 code inclusive

C++ DP速解難題leetcode 3363  Find the Maximum Number of Fruits Collected

[Python解請進]

[codes Leetcode]https://leetcode.com/problems/find-the-maximum-number-of-fruits-collected/solutions/7052876/no-fruits-collected-in-i-j-n-1-for-child-2-3-3ms-beats-100/

[Playlist Dynamic Programming]https://www.youtube.com/watch?v=30yq3fmE6E8&list=PLYRlUBnWnd5K_XYUesV9oc6M9ONXII61T

class Solution:
    def maxCollectedFruits(self, fruits: List[List[int]]) -> int:
        n=len(fruits)
        diag=0
        for i, row in enumerate(fruits):
            diag+=row[i]
        for i in range(n-2):
            fruits[i][n-2-i]=fruits[i][n-3-i]=0
        fruits[n-2][0]=0

        for i in range(1, n-1):
            for j in range(max(i+1, n-i-1), n-1):
                fruits[i][j]+=max(fruits[i-1][j-1], fruits[i-1][j], fruits[i-1][j+1])
            fruits[i][-1]+=max(fruits[i-1][-2], fruits[i-1][-1])
        
        for j in range(1, n-1):
            for i in range(max(j+1, n-j-1), n-1):
                fruits[i][j]+=max(fruits[i-1][j-1], fruits[i][j-1], fruits[i+1][j-1])
            fruits[-1][j]+=max(fruits[-2][j-1], fruits[-1][j-1])

        return diag+fruits[n-2][n-1]+fruits[n-1][n-2]