Dynamic programing stingy on space: 98% time, 83% space.
Intuition\n Describe your first thoughts on how to solve this problem. \nDynamic programming.\n\n# Approach\n Describe your approach to solving the problem. \nF
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nDynamic programming.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nFor each day and ech city we compute the best score possible in order to end up in that city at the end of that day.\nFor each new day we only need the previous day\'s data. So a 1 dimension array is enough, plus one more for computing the next day.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(days * cities^2)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(cities), if we don\'t account for the O((cities+days)*cities) parameters.\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int maxScore(int cities,                      // n = cities\n                 int days,                        // k = days\n                 vector<vector<int>>& stayScore,  // [day][city]\n                 vector<vector<int>>& travelScore // [src_city][dst_city]\n    ) {\n        // yesterday_best[city] hold the best score that we can achieve\n        // and still end up in \'city\' at the beginning of some day.\n        // We use yesterday_best to compute today_best which holds the best\n        // scores at the end of the day.\n        vector<int> yesterday_best(cities, 0);\n        vector<int> today_best(cities, 0);\n        for (int today = 0; today < days; ++today) {\n            for (int new_dest = 0; new_dest < cities; ++new_dest) {\n                int new_score = 0;\n                for (int old_dest = 0; old_dest < cities; ++old_dest) {\n                    int score = yesterday_best[old_dest] +\n                                travelScore[old_dest][new_dest];\n                    if (old_dest == new_dest)\n                        score += stayScore[today][old_dest];\n                    if (score > new_score)\n                        new_score = score;\n                }\n                today_best[new_dest] = new_score;\n            }\n            // For performance reasons we define today_best outside the loop\n            // in order to avoid an expensive and unnecessary 0-initialization\n            // during each iteration. A swap here should be in constant time.\n            std::swap(yesterday_best, today_best);\n        }\n        // After the loop today is the days+1-th day, so pick yesterday\'s max\n        return ranges::max(yesterday_best);\n    }\n};\n```
[]