[python3] easy dp solution + explanation/contest comentary
Intuition and Thoughts\n you\'re just looking for the maximum cell that\'s further to the right or further down from the cell you\'re looking at. \n Gonna be si
#### Intuition and Thoughts\n* you\'re just looking for the maximum cell that\'s further to the right or further down from the cell you\'re looking at. \n* Gonna be size of O(grid) time for each cell if we iterate to get max cell (box with top left at (i,j) and bottom right at (m-1,n-1)), that sucks. \n* If we know the max of one box, can we construct the max for other boxes? hmmm....yes, well just cache them then and use them when we need them.\n* how to traverse the box to get these maxes (so I imagined going from bottom right, and working to the cells neighboring it and then building up these max cells)\n\n#### Contest Solution\n```\nclass Solution:\n    def maxScore(self, grid: List[List[int]]) -> int:\n        \n        @cache\n        def dp(i,j): # largest from top left (i,j) to (M-1,N-1)\n            if i >= M or j >= N:\n                return -inf\n            return max(grid[i][j], dp(i+1,j), dp(i,j+1))\n        \n        M = len(grid)\n        N = len(grid[0])\n        \n        res = -inf\n        for i in range(M):\n            for j in range(N):\n                n = grid[i][j]\n                res = max(res, dp(i+1,j)-n, dp(i,j+1)-n)\n        return res\n```
[]