Python Dict memo doesnt work! Use 2D lists!
Story\nI used a Dictionary to store the memo values and it resulted in TLE.\nThen I used a 2D Matrix (List of Lists) and it worked.\n\n---\n- Python3 Dict: TLE\
# Story\nI used a **Dictionary** to store the memo values and it resulted in **TLE**.\nThen I used a **2D Matrix (List of Lists)** and it worked.\n\n---\n- Python3 Dict: **TLE**\n- Python3 List: **12499 ms**\n- C++ vector<vector<int>>: **628 ms**\n\nConclusion: Use **C++**;\n\n\n# Code\n```python3 [Python3 (Dict Memo)]\n# This code results in TLE\n\nclass Solution:\n    def maxScore(self, n: int, k: int, stayScore: List[List[int]], travelScore: List[List[int]]) -> int:\n        memo = {}\n        def dfs(days_remain, day_id, city_id):\n            # base cases\n            if days_remain == 0:\n                return 0\n\n            if (day_id, city_id) in memo:\n                return memo[(day_id, city_id)]\n            \n            # both options consume one day: days_remain-1 and day_id+1 and give a score\n            maxx = 0\n            \n            # option 1: stay in the current city\n            score = dfs(days_remain-1, day_id+1, city_id) + stayScore[day_id][city_id]\n            maxx = max(maxx, score)\n\n            # option 2: move to \'dest_id\' city\n            for dest_id in range(n):\n                if dest_id != city_id: # travel to ANOTHER city\n                    score = dfs(days_remain-1, day_id+1, dest_id) + travelScore[city_id][dest_id]\n                    maxx = max(maxx, score)\n\n            # Save the computed result in memo\n            memo[(day_id, city_id)] = maxx\n            return maxx\n\n        # main\n        maxim = 0\n        for city_id in range(n):\n            maxim = max(maxim, dfs(k, 0, city_id))\n\n        return maxim\n            \n```\n```python3 [Python3 (List Memo)]\n# This one works (12499 ms)\n\nclass Solution:\n    def maxScore(self, n: int, k: int, stayScore: List[List[int]], travelScore: List[List[int]]) -> int:\n        memo = [[-1 for _ in range(n)] for _ in range(k)]\n\n        def dfs(days_remain, day_id, city_id):\n            # base cases\n            if days_remain == 0:\n                return 0\n\n            if memo[day_id][city_id] != -1:\n                return memo[day_id][city_id]\n\n            # both options consume one day: days_remain-1 and day_id+1 and give a score\n            maxx = 0\n            \n            # option 1: stay in the current city\n            score = dfs(days_remain-1, day_id+1, city_id) + stayScore[day_id][city_id]\n            maxx = max(maxx, score)\n\n            # option 2: move to \'dest_id\' city\n            for dest_id in range(n):\n                if dest_id != city_id: # travel to ANOTHER city\n                    score = dfs(days_remain-1, day_id+1, dest_id) + travelScore[city_id][dest_id]\n                    maxx = max(maxx, score)\n\n            # Save the computed result in memo\n            memo[day_id][city_id] = maxx\n            return maxx\n\n        # main\n        maxim = 0\n        for city_id in range(n):\n            maxim = max(maxim, dfs(k, 0, city_id))\n\n        return maxim\n            \n        \n```\n```cpp []\n// finishes in 628 ms\n\nclass Solution {\npublic:\n    int dfs(int days_remain, int day_id, int city_id, int n, int k, vector<vector<int>>& stayScore, vector<vector<int>>& travelScore, vector<vector<int>>& memo) {\n        if(days_remain == 0) {\n            return 0;\n        }\n        \n        // memo hit\n        if(memo[day_id][city_id] != -1) {\n            return memo[day_id][city_id];\n        }\n\n\n        int maxx = 0;\n\n        // option 1: stay in the current city\n        int score = dfs(days_remain-1, day_id+1, city_id, n, k, stayScore, travelScore, memo) + stayScore[day_id][city_id];\n        maxx = max(maxx, score);\n\n        // option 2: move to \'dest_id\' city\n        for(int dest_id=0; dest_id<n; dest_id++) {\n            if(dest_id != city_id) {\n                score = dfs(days_remain-1, day_id+1, dest_id, n, k, stayScore, travelScore, memo) + travelScore[city_id][dest_id];\n                maxx = max(maxx, score);\n            }\n        }\n\n        memo[day_id][city_id] = maxx;\n        return maxx;\n\n    }\n    int maxScore(int n, int k, vector<vector<int>>& stayScore, vector<vector<int>>& travelScore) {\n        // memo[day_id][city_id]\n        // initialize with -1: not filled\n        vector<vector<int>> memo(k, vector<int>(n, -1));\n\n        int maxx = 0;\n        // You can start from any city\n        for(int city_id=0; city_id<n; city_id++) {\n            maxx = max(maxx, dfs(k, 0, city_id, n, k, stayScore, travelScore, memo));\n        }\n\n        return maxx;\n    }\n};\n```
[]