[Python3] Simple dynamic programming
\nclass Solution:\n    def findBall(self, grid: List[List[int]]) -> List[int]:\n        \n        N = len(grid)\n        M = len(grid[0])\n        answer = [[-2
```\nclass Solution:\n    def findBall(self, grid: List[List[int]]) -> List[int]:\n        \n        N = len(grid)\n        M = len(grid[0])\n        answer = [[-2]*M for _ in range(N+1)]\n        \n        for i in range(M):\n            answer[N][i] = i\n    \n        def find_end(i,j):\n            if answer[i][j] == -2:\n                if j < M-1 and grid[i][j] == 1 and grid[i][j+1] == 1:\n                    answer[i][j] = find_end(i+1,j+1)\n                elif j > 0 and grid[i][j] == -1 and grid[i][j-1] == -1:\n                    answer[i][j] = find_end(i+1,j-1)\n                else:\n                    answer[i][j] = -1\n            return answer[i][j]\n            \n        for j in range(M):\n            find_end(0,j)\n            \n        return answer[0]\n```\n\nIf ```answer[i][j]``` is -2, then its value has not been computed. If it is -1, then the bottom is not reachable. Otherwise its value will be the final column the ball reaches.\n\nAt each step, if the ball can move, find_end is recursively called on the next square it falls on. Otherwsie the ball is stuck and we set its value to -1. \n\nTo make the base case easier, for when the end is reached, a row is added to the bottom of answer indicating the corresponding column.
['Dynamic Programming', 'Depth-First Search', 'Memoization', 'Python', 'Python3']