My Solution
\n/**\n * Time Complexity: O(k * n * n)\n * Space Complexity: O(n)\n */\nclass Solution {\n public:\n  int maxScore(const int n,\n               const int k,\n 
```\n/**\n * Time Complexity: O(k * n * n)\n * Space Complexity: O(n)\n */\nclass Solution {\n public:\n  int maxScore(const int n,\n               const int k,\n               const vector<vector<int>> &stayScore,\n               const vector<vector<int>> &travelScore) {\n    constexpr int range = 2;\n    int dp[range][n];\n    memset(dp, 0, sizeof(dp));\n    int previous = 0;\n    int current = 1;\n    for (int day = 0; day < k; ++day) {\n      for (int current_city = 0; current_city < n; ++current_city) {\n        for (int previous_city = 0; previous_city < n; ++previous_city) {\n          if (previous_city == current_city) {\n            dp[current][current_city] = max(dp[current][current_city],\n                                            dp[previous][previous_city] + stayScore[day][current_city]);\n          } else {\n            dp[current][current_city] = max(dp[current][current_city],\n                                            dp[previous][previous_city] + travelScore[previous_city][current_city]);\n          }\n        }\n      }\n\n      previous ^= 1;\n      current ^= 1;\n      memset(dp[current], 0, sizeof(dp[current]));\n    }\n    return *max_element(dp[previous], dp[previous] + n);\n  }\n};\n```
[]