Easy to understand memo DP solution
Intuition\nThe problem requires maximizing points by choosing to either stay in a city or travel to another city each day. The choice depends on the stay score 
# Intuition\nThe problem requires maximizing points by choosing to either stay in a city or travel to another city each day. The choice depends on the stay score of the current city and travel score to another city. We can approach this with dynamic programming since the problem has overlapping subproblems and optimal substructure.\n\n# Approach\n1. **Define DP State**: Let `dp[curCity][curDay]` represent the maximum points achievable from `curCity` starting on `curDay`.\n2. **Base Case**: When `curDay` exceeds `totDays`, return 0, as no more points can be earned.\n3. **Recursive Transition**:\n   - **Stay Option**: Earn points by staying in the same city, which adds `stayScore[curDay][curCity]`.\n   - **Travel Option**: Explore traveling to other cities. For each city `i` (other than `curCity`), add the `travelScore` for moving to that city plus the result of recursively calling the function from the new city.\n4. **Memoization**: Use a 2D array `dp` to store results and avoid recomputation.\n\n5. **Final Calculation**: Iterate over each city as the starting city on day 0 to get the maximum points achievable.\n\n# Complexity\n- **Time complexity**: $$O(n^2 \\times k)$$ where \\( n \\) is the number of cities and \\( k \\) is the number of days, since we evaluate each combination of city and day once and potentially compare each city for travel options.\n- **Space complexity**: $$O(n \\times k)$$ due to the memoization table storing results for each city-day combination.\n\n\n# Code\n```cpp []\nclass Solution {\nprivate:\n    int travelOrStay(vector<vector<int>>& dp, int curCity, int totCities,\n                     int totDays, vector<vector<int>>& stayScore,\n                     vector<vector<int>>& travelScore, int curDay) {\n        if (curDay >= totDays) {\n            return 0;\n        }\n        if (dp[curCity][curDay] != -1) {\n            return dp[curCity][curDay];\n        }\n        // Stay at current city\n        int stayPoints = stayScore[curDay][curCity] +\n                         travelOrStay(dp, curCity, totCities, totDays,\n                                      stayScore, travelScore, curDay + 1);\n\n        // Travel to other cities\n        int travelPoints = 0;\n        for (int i = 0; i < totCities; i++) {\n            if (i != curCity) {\n                int points = travelScore[curCity][i] +\n                             travelOrStay(dp, i, totCities, totDays, stayScore,\n                                          travelScore,\n                                          curDay + 1); // Advance the day\n                travelPoints = max(travelPoints, points);\n            }\n        }\n        return (dp[curCity][curDay] = max(stayPoints, travelPoints));\n    }\n\npublic:\n    int maxScore(int n, int k, vector<vector<int>>& stayScore,\n                 vector<vector<int>>& travelScore) {\n        int points = 0;\n        vector<vector<int>> dp(n, vector<int>(k, -1));\n        // Start from every city\n        for (int i = 0; i < n; i++) {\n            points = max(points,\n                         travelOrStay(dp, i, n, k, stayScore, travelScore, 0));\n        }\n        return points;\n    }\n};\n\nauto init = []() {\n    ios_base::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return 0;\n}();\n```
[]