[Python3] Beat 100% Runtime 100% Memory
Intuition\nNative dynamic programming, while dp[i][j] represents the max score can be earned at day i landing in city j.\n\n# Approach\nNeed to think about init
# Intuition\nNative dynamic programming, while `dp[i][j]` represents the max score can be earned at day `i` landing in city `j`.\n\n# Approach\nNeed to think about initialization and transfer function.\n\n### Initialization \nAt day 0, when landing at city `j`, it could be either stay at city `j` to move from a different city `j2`.\n$$dp[0][j] = max(stay\\_score[0][j], max(travel\\_score[j2][j]))$$, for all $$j2 != j$$.\n\n### Transfer Function\nAt day `i`, similar to initialization, but this time the max score already earned at day `i-1` at last city `j2` needs to be included.\n$$dp[i][j] = max(stay\\_score[i][j], max(travel\\_score[j2][j]))$$, for all $$j2 != j$$.\n\nSince the transfer function only needs to consider data under `i-1`, so all rows above `i-1` is not required, memory usage can be improved by rotating `dp` to be a at-most 2-row array, representing last day\'s data and current day\'s.\n\n# Complexity\n- Time complexity:\n$$O(n^2 * k)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```python3 []\nclass Solution:\n    def maxScore(self, n: int, k: int, stay_score: List[List[int]], travel_score: List[List[int]]) -> int:\n        # dp[i][j]: max score can earn with i actions ending at city j.\n        # n = 3, k = 2, stay_score = [[3,4,2],[2,1,2]], travel_score = [[0,2,1],[2,0,4],[3,2,0]]\n        # 3, 4, 4\n        # max((3+2), (4+2), (4+3)), max((3+2), (4+1), (4+2)), max((3+1), (4+4), (4+2))\n\n        dp = [[0 for _ in range(n)] for _ in range(min(2, k))]\n\n        # Initilization, assign value to dp[0][:]\n        # It can be either stay at city j or travel from a different city j2 to city j\n        # Pick up the maximum one.\n        for j in range(n):\n            max_travel_score = 0\n            for j2 in range(n):\n                max_travel_score = max(max_travel_score, travel_score[j2][j])\n            dp[0][j] = max(stay_score[0][j], max_travel_score)\n        \n        # For every action after day 0,\n        # Similar to initilization, \n        # it can be either stay at city j or travel from a different city j2 to city j\n        # But this time remember to add score max score earned at day i-1 at last city\n        for i in range(1, k):\n            i_ind = i % 2\n            for j in range(n):\n                for j2 in range(n):\n                    dp[i_ind][j] = max(dp[i_ind][j], dp[1-i_ind][j2]+travel_score[j2][j]) if j2 != j else max(dp[i_ind][j], dp[1-i_ind][j2]+stay_score[i][j])\n        \n        if len(dp) > 1:\n            return max(max(dp[0]), max(dp[1]))\n        else:\n            return max(dp[0])\n```
[]