[Python3] Top Down Memoization and Bottom Up DP
CodeTop Down memozationBottom up DP

# Code

Top Down memozation
```python3 
class Solution:
    def maxScore(self, n: int, k: int, stayScore: List[List[int]], travelScore: List[List[int]]) -> int:
        dp = [[None] * (k + 1) for _ in range(n)]
        def recurse(i, k):
            if k == -1: return 0

            if dp[i][k] is not None: return dp[i][k]
            possible_travel = [travelScore[j][i] + recurse(j, k - 1) for j in range(n) if j != i]
            dp[i][k] = max(
                stayScore[k][i] + recurse(i, k - 1),
                max(possible_travel) if possible_travel else float('-inf')
            )
            return dp[i][k]

        ans = max([recurse(i, k - 1) for i in range(n)])
        return ans
```

Bottom up DP

```python3 []
class Solution:
    def maxScore(self, n: int, k: int, stayScore: List[List[int]], travelScore: List[List[int]]) -> int:
        dp = [[None] * (n) for _ in range(k + 1)]
        dp[0] = [0] * n

        for i in range(1, k + 1):
            for j in range(n):
                dp[i][j] = dp[i - 1][j] + stayScore[i - 1][j]
                for prev_idx in range(n):
                    if prev_idx == j: continue
                    dp[i][j] = max(
                        dp[i][j],
                        travelScore[prev_idx][j] + dp[i - 1][prev_idx] 
                    )
        return max(dp[-1])
```
                    
['Python3']