numpy-accelerated DP
Intuition\nDP with states being the maximum points one can get by ending up at jth city on the ith day.\n\n# Approach\nUpon closer look, the "stay" option can b
# Intuition\nDP with states being the maximum points one can get by ending up at `j`th city on the `i`th day.\n\n# Approach\nUpon closer look, the "stay" option can be computed with array addition while the "travel" option can be computed with broadcasted array addition. The updated states can then be computed with max & maximum within the "travel" option & between the "stay" and "travel" options, respectively.\n\n# Complexity\n- Time complexity:\n$$O(n^2k)$$ but small constant due to vectorization. This clocked at 804 ms.\n\n- Space complexity:\n$$O(n^2)$$\n\n# Code\n```python3 []\nimport numpy as np\n\nclass Solution:\n    def maxScore(self, n: int, k: int, stayScore: List[List[int]], travelScore: List[List[int]]) -> int:\n        curr = np.array([0] * n)\n        travel = np.array(travelScore)\n        for stay in stayScore:\n            stay = np.array(stay) + curr\n            trav = curr[:, None] + travel\n            trav = np.max(trav, axis=0)\n            curr = np.maximum(stay, trav)\n        return max(curr)\n```
[]